小易定义一个数字序列是完美的,当且仅当对于任意,都满足,即每个数字都要大于等于前面所有数字的和。
现在给定数字序列,小易想请你从中找出最长的一段连续子序列,满足它是完美的。
第一行数据组数。对于每组数据,第一行一个整数,接下来一行个整数表示序列。
对于每组数据,一行一个数字表示最长完美的连续子序列的长度。
2 5 1 3 9 2 6 5 4 2 9 16 7
3 3
import sys def find_longest(l): i, j = 0, 1 cur = 0 while j < len(l) and i < len(l): while j < len(l) and sum(l[i:j]) <= l[j]: j += 1 cur = max(cur, j - i) i = j j = i + 1 return cur n = int(sys.stdin.readline()) for i in range(n): size = int(sys.stdin.readline()) a = list(map(int, sys.stdin.readline().split())) print(find_longest(a))
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); while(T-- > 0){ int n = sc.nextInt(); int[] nums = new int[n]; for(int i = 0; i < n; i++) nums[i] = sc.nextInt(); System.out.println(solve(nums)); } } // 直接用滑动窗口计算窗口内的元素之和来判断 private static int solve(int[] nums) { int left = 0, right = 1; long sum = nums[0]; int maxLen = 0; while(right < nums.length){ if(nums[right] >= sum){ maxLen = Math.max(maxLen, right - left + 1); sum += nums[right]; right ++; }else{ sum -= nums[left]; left ++; } } return maxLen; } }
public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); while(m-- > 0) { int n = sc.nextInt(); int[] nums = new int[n]; for(int i = 0; i < n; i++) { nums[i] = sc.nextInt(); } System.out.println(longestSub(nums)); } } public static int longestSub(int[] nums) { int i = 0, j = 1, max = 0, sum = nums[0],n = nums.length; while(j < n) { if(nums[j] >= sum) { sum += nums[j]; max = Math.max(max, j-i+1); j++; } else { sum -= nums[i]; i++; } } return max; }
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int t = scanner.nextInt(); for (int i = 0; i < t; i++) { int j = scanner.nextInt(); int[] arr = new int[j]; for (int i1 = 0; i1 < j; i1++) { arr[i1] = scanner.nextInt(); } System.out.println(demo4(arr)); } } //2 3 5 9 18 public static int demo4(int[] arr) { //两个辅助指针,标记从哪里开始 int left = 0; int right = 1; //最大子序列长度 int maxCount = 1; //当前子序列长度 int curCount = 1; int sum = arr[0]; //当右边指针未达到数组最右边边界时 while (right < arr.length) { //如果满足条件 if (arr[right] >= sum) { //将当前值加入总和 sum += arr[right]; //当前子序列的长度 curCount = right - left + 1; //right指针向后移动一位 right++; //更新最大长度 maxCount = maxCount > curCount ? maxCount : curCount; } else { //如果不满足条件,则需要从sum中减去left所在位置的值 sum -= arr[left]; //将left向后移动一位 left++; } } return maxCount; } }
#include <iostream> using namespace std; int main() { int n, m; cin >> n; while(n--) { cin >> m; int nums[m]; int start = 1; int res = 0; for(int i = 0; i < m; i++) { cin >> nums[i]; } int sum = nums[0]; for(int i = 1; i < m; i++) { if(sum <= nums[i]) { sum += nums[i]; res = max(res, i - start + 1); }else { start = i; sum = nums[i]; } } cout << res << endl; } }
#include<vector> #include<iostream> using namespace std; vector<int> solution(vector<vector<int> >&input){ vector<int> res; for(int i = 0; i < input.size(); i++){ int left = 0; int sum = 0; int len = 0; for(int j = 0; j < input[i].size()-1; j++){ sum += input[i][j]; if(sum > input[i][j+1]){ len = max(len, j- left+1); left = j+1; sum = 0; } } if(len == 0) len = input[i].size(); res.push_back(len); } return res; } int main(){ int a; cin >> a; vector<vector<int> > input; for(int i = 0; i < a; i++){ int b; cin >> b; vector<int> temp; int number; for(int i = 0; i < b; i++){ cin >> number; temp.push_back(number); } input.push_back(temp); } vector<int> res = solution(input); for(auto cha : res) cout << cha << endl; return 0; }
T = int(input()) list1 = [] for i in range(T): n = int(input()) list1.append(list(map(int,input().split()))) for i in range(T): sum = 0 num = 0 num_list = [] for value in list1[i]: if sum <= value : sum = sum + value num = num + 1 num_list.append(num) else: num = 1 sum = value print(max(num_list)) #提示出错的案例单独运行就是正确答案,生气
using System; using System.Collections; using System.Collections.Generic; using System.Text; public class Program { public static void Main(string[] args) { int T = int.Parse(Console.ReadLine()); for(int k = 0; k < T; ++k) { int n = int.Parse(Console.ReadLine()); string[] ipts = Console.ReadLine().Split(' '); int[] ar = new int[n]; for (int i = 0; i < n; ++i) ar[i] = int.Parse(ipts[i]); long sum = 0; int len = 1; int tempLen = 1; for(int i = 0; i < n; ++i) { sum = ar[i]; tempLen = 1; for(int j = i + 1; j < n; ++j) { if (ar[j] >= sum) { ++tempLen; sum += ar[j]; } else break; } len = Math.Max(len, tempLen); } Console.WriteLine(len); } } }
#include<stdio.h> #include<stdlib.h> void sort(int *a, int l)//a为数组地址,l为数组长度。 { int i, j; int v; //排序主体 for(i = 0; i < l - 1; i ++) for(j = i+1; j < l; j ++) { if(a[i] > a[j])//如前面的比后面的大,则交换。 { v = a[i]; a[i] = a[j]; a[j] = v; } } } int main() { int T, n, m; int XL[100000]; int XB[100000] = {0}; int pm = 1; // 序列长度 int sum = 0; scanf("%d", &T); while(T--) { scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d", &XL[i]); } sort(XL, n); // 2 4 7 9 16 for(int i = 1; i <= n; i++) { for(int j = 0; j < i; j++) { if(XB[j] != 1) { sum += XL[j]; } } if(sum < XL[i]) { pm += 1; } else { XB[i+1] = 1; } sum = 0; } printf("%d\n", pm); pm = 0; } return 0; }测试对的,但是提交一个也没有对
照着官方Java答案写的C++版本,代码能知道在干嘛,但是我暂时不知道为什么用双指针滑动窗口是对的
希望有知道的牛友解答一下
int prefectSequence(vector<int>& input) { int left = 0, right = 1; long sum = input[0]; int maxLen = 0; while (right < input.size()) { if (input[right] >= sum) { maxLen = max(maxLen, right - left + 1); sum += input[right]; right++; } else { // 这里就是我搞不懂的地方了 // 我不理解为什么这里双指针滑动窗口的正确的 sum -= input[left]; left++; } } return maxLen; } int main() { int T,n,num; cin >> T; vector<int> input; while (T-- >0) { cin >> n; for (int i = 0; i < n; i++) { cin >> num; input.push_back(num); } cout<<prefectSequence(input) << endl; input.clear(); } return 0; }
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int MAXN = 1e5 + 50; int a[MAXN]; int main() { int T, n; cin >> T; while (T--) { cin >> n; for (int i = 0; i < n; ++i) cin >> a[i]; LL curr = a[0]; int ans = 0; for (int l = 0, r = 1; r < n; ++r) { while (curr > a[r]) { curr -= a[l++]; } ans = max(ans, r - l + 1); curr += a[r]; } cout << ans << endl; } return 0; }
T = int(input()) while T: T -= 1 n = int(input()) nums = list(map(int,input().split())) i = 0 j = 1 res = 0 sum = nums[0] while j < n: if nums[j] >= sum: sum += nums[j] res = max(res, j-i+1) j+=1 else: sum -= nums[i] i+=1 print(res)
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); while(t--!=0){ int n = sc.nextInt(); int[] nums = new int[n]; for(int i = 0 ; i < n ; i ++ ) nums[i] = sc.nextInt(); int l = 0 ; int len = 0 ; int sum = 0 ; for(int i = 0 ; i < n ;){ if( sum <= nums[i]){ sum += nums[i]; i++; } else{ len = Math.max(len,i - l ); sum -= nums[l]; l++; if(l > i) i++; } } len = len == 0 ? n : len ; System.out.println(len); } } }
from functools import reduce n=int(input()) for niter in range(n): nlong = int(input()) a = list(map(int,input().split())) judge=[] for i in range(0,len(a)+1): k=i+1 l=1 while True: if k<len(a) and a[k]>=reduce(lambda x,y:x+y,a[i:k]): k = k+1 l=l+1 else: break judge.append(l) print(max(judge))
t = int(input()) for _ in range(t): n = int(input()) li = list(map(int, input().split(" "))) result = left = 0 left_sum = 0 for i in range(1, len(li)): left_sum += li[i - 1] while li[i] < left_sum and left < i: left_sum -= li[left] left += 1 result = max(result, i - left + 1) print(result)
#include<iostream> using namespace std; const int maxn = 100005; int arr[maxn]; int main() { int T, n, sum, ans, left, right; scanf("%d", &T); while(T--) { left = right = sum = ans = 0; scanf("%d", &n); for(int i = 0; i < n; ++i) scanf("%d", &arr[i]); while(right < n) { while(right < n && sum <= arr[right]) sum += arr[right++]; ans = max(ans, right - left); if(right >= n) break; while(sum > arr[right]) sum -= arr[left++]; } printf("%d\n", ans); } }
data = [] length = int(input()) * 2 x = 0 while x < length: s = input() if s != "": temp = [int(i) for i in s.split()] data.append(temp) x += 1 else: break i = 0 while i < length: n = data[i ][0] lst = data[i + 1] j = 1 s = lst[0] while j <= n: if s > lst[j]: break else: s += lst[j] j += 1 print (j) i += 2
#include <iostream> (720)#include <vector> using namespace std; int main() { int t; cin >>t; vector<vector<int>> arr(t); for (int i = 0;i < t;i++) { int len; cin >> len; for (int j= 0;j < len;j++) { int a; cin >> a; arr[i].push_back(a); } } vector<int> maxlen(t,0); for (int i = 0;i < t;i++) { int left=0,sum = 0,len = 0; while (left <arr[i].size()) { for (int j = left;j < arr[i].size();j++) { if (arr[i][j] >= sum) { sum += arr[i][j]; len++; maxlen[i] = len > maxlen[i] ? len : maxlen[i]; } else { sum = 0; len = 0; break; } } left++; } } for (int i = 0;i < maxlen.size(); ++i) { cout << maxlen[i]<< " "; cout << endl; } return 0; }