寻找一个序列中和不小于S的最短子序列，n的时间预处理出前缀和，然后枚举末位置二分初始位置nlogn搞定
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 |
#include <cstdio>#include <cstring>#include <algorithm>using
namespace std;const
int maxn = 100001;int A[maxn],B[maxn];int
main() { int
n,S; while(~scanf("%d%d",&n,&S)) { int
ans = 0; for(int
i = 1;i <= n;i++) { scanf("%d",&A[i]); B[i] = B[i - 1] + A[i]; int
str = 1,end = i; while(str < end) { int
mid = str + (end - str + 1) / 2; if(B[i] - B[mid - 1] < S) { end = mid - 1; } else
{ str = mid; } } if(B[i] - B[str - 1] >= S) { if(ans == 0) ans = i - str + 1; else
ans = min(ans,i - str + 1); } } printf("%d\n",ans); } return
0;} |
原文：http://www.cnblogs.com/rolight/p/3551177.html