题目来源：http://poj.org/problem?id=3061
【题意】给定长度为n的数列整数，以及整数s,求出总和不小于s的连续子序列的长度的最小值，如果解不存在，则输出0。
【思路1】求出其前缀和，for循环（确定了左边界）+二分搜索（为了确定右边界），算是暴力，复杂度为O(nlogn）。
【代码】
#include<cstdio> #include<cstring> #include<algorithm> #include<string> #include<cmath> #include<iostream> #include<map> #include<queue> using namespace std; typedef long long LL; const double INF=1e9; int n,s; LL a[100000+10]; int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&s); memset(a,0,sizeof(a)); for(int i=0; i<n; i++) { scanf("%lld",&a[i+1]); a[i+1]+=a[i]; } if(a[n]<s) { printf("0\n"); continue; } int res=n; for(int i=0; a[i]+s<=a[n]; i++) { int f=lower_bound(a+i,a+n,a[i]+s)-a; res=min(res,f-i); } printf("%d\n",res); } } 【思路2】 假设用a数组存下输入的数字，若存在s，使得以a[s]开始总和最初大于S时的连续子序列a[s]+...+a[t-1],这时a[s+1]+...+a[t-2]<a[s]+...+a[t-2]<S; 利用这个性质就可以设计如下算法：
（1）以s=t=sum=0初始化。
（2）只要依然有sum<S，就不断将sum增加a[t]，并将t增加1。
（3）如果（2）中无法满足sum>=s则终止，否则的话，更新res=min(res,t-s)。对于这个算法，由于t最多变换n次，因此只需要O（n）的复杂度就可以求解这个问题了。
#include<cstdio> #include<cstring> #include<algorithm> #include<string> #include<cmath> #include<iostream> #include<map> #include<queue> using namespace std; typedef long long LL; const double INF=1e9; int a[100000+10]; int main() { int T,n,S; scanf("%d",&T); while(T--) { memset(a,0,sizeof(a)); scanf("%d%d",&n,&S); for(int i=0; i<n; i++) scanf("%d",&a[i]); int s=0,sum=0,t=0,res=n+1; for(;;) { while(t<n&&sum<S) { sum+=a[t++]; } if(sum<S) break; res=min(res,t-s); sum-=a[s++]; } if(res>n) res=0; printf("%d\n",res); } }
