思路: 尺取法

注意本题目中所有的内容全部是证书, 这就为我们维护了一个很好的单调性. 考虑最暴力的\(\mathcal O(n^3)\)的做法, 就是枚举起点, 终点, 然后分别求和. 但是我们可以做的好一点.

假设现在我们有这样的一个情况:

+---+---+---+---+---+---+
^l          ^r
   sum[l..r]<S

但是

+---+---+---+---+---+---+
^l              ^r
    sum[l..r]<S

那么下一次, \(r\)不用往右移了. \(l\)只要往右移一位, \(l\)不用变就行了. 因为这样做相当于构建一个子区间, 维护了单调性, 那么就可以做了.

+---+---+---+---+---+---+
    ^l          ^r
      sum[l..r]?

Code

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 100005
#define F(i, a, b) for(int i=a; i<=b;i++)
#define Fd(i, a, b) for(int i=a;i>=b;i--)

int n, s, a[MAXN];
void solve(){
	memset(a, 0, sizeof a);
	cin>>n>>s;
	F(i, 1, n) cin>>a[i];
	int len = 1145141;
	int r = 0, sum =0;
	for(int l=1;l<=n;l++){
		while(r<=n && sum <s){
			r++; sum += a[r];
		}
		if(sum >= s){
			len = min(len, r-l+1);
		}
		sum -= a[l];
	}
	if(len == 1145141) cout<<"0\n";
	else cout<<len<<"\n";
}
int main(){
	cin.tie(NULL);
	int T; cin>>T; while(T--) solve();
	return 0;
}