有一个正整数序列，求最短的子序列使得其和大于等于S，并输出最短的长度。
用数组b[i]存放序列的前i项和，所以b[i]是递增的。
遍历终点j，然后在区间[0, j)里二分查找满足b[j]-b[i]≥S的最大的i，时间复杂度为O(nlongn)。
这里二分查找用到库函数lower_bound()
//#define LOCAL
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = + ;
int a[maxn], b[maxn]; int main(void)
{
#ifdef LOCAL
freopen("2678in.txt", "r", stdin);
#endif int n, S;
while(scanf("%d%d", &n, &S) == )
{
for(int i = ; i <= n; ++i)
{
scanf("%d", &a[i]);
b[i] = b[i-] + a[i];
}
int ans = n + ;
for(int j = ; j <= n; ++j)
{
int i = lower_bound(b, b+j, b[j]-S) - b;
if(i > )
ans = min(ans, j-i+);
}
printf("%d\n", ans == n+ ? : ans);
}
return ;
}
代码君一
继续优化：
由于j是递增的，bj也是递增的，所以bi-1≤bj-S的右边也是递增的。换句话说满足条件的i的位置也是递增的。
虽然有两层循环，但是i的值只增不减，所以时间复杂度为O(n)
//#define LOCAL
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = + ;
int a[maxn], b[maxn]; int main(void)
{
#ifdef LOCAL
freopen("2678in.txt", "r", stdin);
#endif int n, S;
while(scanf("%d%d", &n, &S) == )
{
for(int i = ; i <= n; ++i)
{
scanf("%d", &a[i]);
b[i] = b[i-] + a[i];
}
int ans = n + ;
int i = ;
for(int j = ; j <= n; ++j)
{
if(b[i-] > b[j] - S)
continue;
while(b[i] <= b[j] - S)
++i;
ans = min(ans, j-i+);
}
printf("%d\n", ans == n+ ? : ans);
}
return ;
}
代码君二