POJ 3061 - Subsequence

http://poj.org/problem?id=3061

概要

N 項の数列が与えられる．

この中で和が S 以上になるような連続した部分列の最小の長さを答える． ただし，そのような連続した部分列が存在しないときは 0 を答える．

制約

• 10 < N < 10^5
• 0 < 数列の要素 <= 10^4
• S < 10^8

解法

しゃくとりメソッド的にそのような部分列を列挙して最小値をとるだけ．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int T;
 8   scanf("%d", &T);
 9   while (T-- > 0) {
10     int N, S;
11     scanf("%d %d", &N, &S);
12     static int a[100000];
13     for (int i = 0; i < N; i++) {
14       scanf("%d", &a[i]);
15     }
16 
17     int ans = N;
18     int s = 0;
19     int j = 0;
20     for (int i = 0; i < N; i++) {
21       s += a[i];
22       while (j <= i && s >= S) {
23         ans = min(ans, i-j+1);
24         s -= a[j];
25         j++;
26       }
27     }
28     printf("%d\n", ans == N ? 0 : ans);
29   }
30   return 0;
31 }