poj 3061 Subsequence 二分 前缀和 双指针

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <memory.h>
 5 #include <queue>
 6 
 7 
 8 using namespace std;
 9 
10 
11 /*
12 Sample Input
13 6
14 10 15
15 5 1 3 5 10 7 4 9 2 8
16 5 11
17 1 2 3 4 5
18 1 2
19 1
20 1 1
21 5
22 3 9999
23 1 2 3 
24 3 0
25 1 2 3 
26 
27 Sample Output
28 2
29 3
30 */
31 const int MAX_N = 1000010;
32 int n, m;
33 int nums[MAX_N];
34 
35 int ret = MAX_N;
36 
37 void solve()
38 {
39     int sum = 0;
40     int minlen = MAX_N;
41 
42     int r = -1; int l = 0;
43 
44     while (1) {
45         if (sum < m) {
46             r++;
47             if (r >= n) break;
48             sum += nums[r];
49         }
50         else {
51             //sum >= m
52             minlen = min(minlen, r - l + 1);
53             sum -= nums[l];
54             l++;
55             if (l >= n) break;
56             if (l > r) {
57                 r = l;
58                 sum = nums[l];
59             }
60         }
61     }
62 
63 
64     if (minlen == MAX_N) minlen = 0;
65     cout << minlen << endl;
66 }
67 
68 
69 int main()
70 {
71     int loop;
72     cin >> loop;
73     while (loop--) {
74         cin >> n >> m;
75 
76         for (int i = 0; i < n; i++) {
77             cin >> nums[i];
78         }
79         ret = MAX_N;
80         solve();
81     }
82 
83     return 0;
84 }