二分+前缀和法
满足条件的子序列长度在(0,n)之间，sum[x+i]-sum[i]为从从第i个元素开始序列长度为x的元素的和。前缀和可在O(n)的时间内统计
sum[i]的值。再用二分找出满足条件的最小的子序列长度。
#include #include #include #include #include #include #include #include #include #include #define ll __int64 #define INF 0x3fffffff using namespace std; int sum[100005]; int a[100005]; int n,s; bool C(int x) { bool flag=false; for(int i=0;i =s) { flag=true; break; } } if(flag) return true; else return false; } int solve() { int l=0,r=n+1; while(r-l>1) { int mid=(l+r)/2; if(C(mid)) r=mid; else l=mid; } return r; } int main() { int T; //freopen("d:\\Test.txt","r",stdin); cin>>T; while(T--) { cin>>n>>s; for(int i=0;i 尺取法 （1） 设置两个指针s和t，一开始都指向数列第一个元素，此外sum=0,res=0； （2） 只要sum （3） 直到sum>=S，更新res=min(res,t-s)； （4） 将sum减去一个元素，s加1，执行（2）。 上述流程反复地推进区间的开头和末尾，来求取满足条件的最小区间。 #include #include #include #include using namespace std; int n,m; int a[100005]; void solve() { int res=n+1; int s=0,t=0,sum=0; while(true) { while(t n) res=0; cout< >T; while(T--) { cin>>n>>m; for(int i=0;i
（1） 设置两个指针s和t，一开始都指向数列第一个元素，此外sum=0,res=0； （2） 只要sum （3） 直到sum>=S，更新res=min(res,t-s)； （4） 将sum减去一个元素，s加1，执行（2）。 上述流程反复地推进区间的开头和末尾，来求取满足条件的最小区间。
#include #include #include #include using namespace std; int n,m; int a[100005]; void solve() { int res=n+1; int s=0,t=0,sum=0; while(true) { while(t n) res=0; cout< >T; while(T--) { cin>>n>>m; for(int i=0;i