题目链接：http://poj.org/problem?id=3061
题意：给一个长为n的数列和整数s，求一个连续的子序列，使得这个子序列长度最短并且不小于这个整数s。
统计[1~i]的子序列和sum(i)，(sum(0)=0)。然后求一个区间[i,j]的和即为sum(j)-sum(i-1) (i > 0)。
由于给定序列没有负数，因此sum是个严格不减的序列。
转换成一个求最大值最小的问题，可以二分枚举序列长度，在前缀和上计算子序列[i-1,i+m-1]的和。如果存在一个满足子序列和≥s的，则缩小序列长度并记下当前值，反之扩大。复杂度为O(nlgn)。
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath> using namespace std; const int maxn = ;
int n, s;
int x[maxn];
int sum[maxn]; bool ok(int mm) {
for(int i = ; i <= n - mm + ; i++) {
// printf("%d %d\n", i-1, i+mm-1);
if(sum[i+mm-] - sum[i-] >= s) return ;
}
return ;
} int main() {
// freopen("in", "r", stdin);
int T;
scanf("%d", &T);
while(T--) {
memset(sum, , sizeof(sum));
scanf("%d %d", &n, &s);
for(int i = ; i <= n; i++) {
scanf("%d", &x[i]);
sum[i] = sum[i-] + x[i];
}
if(sum[n] < s) {
printf("0\n");
continue;
}
int ans;
int ll = ;
int rr = n;
while(ll <= rr) {
int mm = (ll + rr) >> ;
if(ok(mm)) {
ans = mm;
rr = mm - ;
}
else ll = mm + ;
}
printf("%d\n", ans);
}
}
此题也可以用尺取法，维护两个指针从左到右扫描所存序列，复杂度为O(n)。
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath> using namespace std; const int maxn = ;
int n, s;
int x[maxn]; int main() {
// freopen("in", "r", stdin);
int T;
scanf("%d", &T);
while(T--) {
scanf("%d %d", &n, &s);
int sum = ;
for(int i = ; i <= n; i++) {
scanf("%d", &x[i]);
sum += x[i];
}
if(sum < s) {
printf("0\n");
continue;
}
int ans = 0x7f7f7f;
int ll = ;
int rr = ;
sum = ;
while() {
while(rr <= n && sum <= s) {
sum += x[rr++];
}
if(sum < s) break;
ans = min(ans, rr-ll);
sum -= x[ll++];
}
printf("%d\n", ans);
}
}