求长度最短的连续序列 它的和大于等于s 输出长度
枚举起点和终点会超时
求出前缀和 都是正整数 所以前缀和是递增的
如果对于前缀和 sum[i]要使得长度最小 那么应该找出最大的j 使得 sum[i]-sum[j]>=s sum[j] <= sum[i]-s 即二分sum[i]-s 找到最大的sum[j]
#include#include #include using namespace std; const int maxn = 100010; int a[maxn]; int sum[maxn]; int main() { int n, s; while(scanf("%d %d", &n, &s) ==2 ) { for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); sum[i] = sum[i-1] + a[i]; } int ans = n+1; for(int i = 1; i <= n; i++) { int l = 0; int r = i; int k = sum[i] - s; if(k < 0) continue; while(l <= r) { int m = (l + r) >> 1; if(sum[m] <= k) l = m + 1; else r = m - 1; } ans = min(ans, i-l+1); } if(ans == n+1) ans = 0; printf("%d\n", ans); } return 0; }