Codeforces 660 C. Hard Process (尺取)

题目链接：http://codeforces.com/problemset/problem/660/C

尺取法

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     static int num[int(3e5 + 5)];
 6     int n, k;
 7     scanf("%d %d", &n, &k);
 8     for(int i = 1; i <= n; ++i) {
 9         scanf("%d", num + i);
10     }
11     int l = 1, res = 0, cnt = 0, flagl = 0, flagr = -1;
12     for(int i = 1; i <= n; ++i) {
13         if(num[i]) {
14             if(i - l + 1 > res) {
15                 res = i - l + 1, flagl = l, flagr = i;
16             }
17         } else {
18             cnt++;
19             while(cnt > k && l <= i) {
20                 if(!num[l++])
21                     --cnt;
22             }
23             if(i - l + 1 > res) {
24                 res = i - l + 1, flagl = l, flagr = i;
25             }
26         }
27     }
28     for(int i = flagl; i <= flagr; ++i)
29         num[i] |= 1;
30     printf("%d
", res);
31     for(int i = 1; i <= n; ++i) {
32         printf("%d%c", num[i], i == n ? '
': ' ');
33     }
34     return 0;
35 }