【题解】LA 2678【Subsequence】

分析

显然一看题就可以得到一个$O(n^3)$的大暴力,前缀和优化后可以到$O(n^2)$,显然TLE是必然的,二分之后可以优化到$O(n\log n)$,不过这不是最优的。
因为$j$是递增的,所以$B_{i-1}\leq B_{j}-s$的右边也是递增的。这样就可以优化的$O(n)$

代码

#include<cstdio>
#include<algorithm>
using std::min;
const int MAXN = 100000 + 6;
int B[MAXN],A[MAXN];

int main(){
    int n,s;
    while(scanf("%d %d",&n,&s) != EOF){
        B[0] = 0;
        for(int i = 1;i <= n;i++) scanf("%d",&A[i]),B[i] = B[i - 1] + A[i];
        int ans = n + 1,i = 1;
        for(int j = 1;j <= n;j++){
            if(B[i - 1] > B[j] - s) continue;
            while(B[i] <= B[j] - s) i++;
            ans = min(ans,j - i + 1);
        }
        printf("%d\n",ans == n + 1 ? 0 : ans);
    }

    return 0;
}