题意：有n个正整数组成一个序列，给定整数S，求长度最短的连续序列，使得他们的和大于等于S
分析：设输入的序列为A[i], i=1..n, 构造前缀数组B[j], j=1..n, B[j]=B[j-1]+A[j], 规定B[0]=0, 当B[j]-B[i-1]>=s的时候i增加，直至B[j]-B[i]<s, 然后更新最短的满足条件的序列的长度j-i+1，复杂度为O（n）
代码：
View Code
1 #include <stdio.h> 2 #include <iostream> 3 using namespace std; 4 #define DEBUG 5 const int MAXN = 100000 + 10; 6 int a[MAXN]; 7 int b[MAXN]; 8 int min(int a, int b){ 9 return a<b?a:b; 10 } 11 int main(){ 12 #ifndef DEBUG 13 freopen("in.txt", "r", stdin); 14 #endif 15 int n, s; 16 while(scanf("%d%d", &n, &s)!=EOF){ 17 int i; 18 b[0]=0; 19 for(i=1; i<=n; i++){ 20 scanf("%d", &a[i]); 21 b[i] = b[i-1] + a[i]; 22 } 23 int ans=n+1; 24 i=1; 25 int j; 26 for(j=1; j<=n; j++){ 27 if(b[i-1]>b[j]-s) continue; 28 while(b[i]<=b[j]-s) i++; 29 ans = min(ans, j-i+1); 30 } 31 if(ans==n+1) ans=0; 32 printf("%d\n", ans); 33 } 34 return 0; 35 }
如果暴力，O（n3）显然不行；如果用upper_bound则为O（n*log(n))
