[CF660C]Hard Process(尺取法)-白红宇

[CF660C]Hard Process(尺取法)

阅读量：4942 次

发布时间：2019-06-11

本文共 1228 字，大约阅读时间需要 4 分钟。

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

尺取法，每次遇到0的时候补一个1，直到补完或者越界为止。之后每次从左向右回收一个0点。记录路径用两个指针卡住，每次更新即可。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               
                12 #include 
                
                 13 #include 
                 
                  14 #include 
                  
                   15 #include 
                   
                    16 #include 
                    
                     17 #include 
                     18 #include 
                      
                       19 20 using namespace std;21 22 const int maxn = 666666;23 int n, k;24 int a[maxn];25 26 int main() {27 // freopen("in", "r", stdin);28 while(~scanf("%d %d", &n, &k)) {29 for(int i = 1; i <= n; i++) {30 scanf("%d", &a[i]);31 }32 int ll = 1;33 int rr = 1;34 int al = 0;35 int ar = 0;36 int cur = 0;37 int ans = 0;38 while(1) {39 if(rr > n) break;40 while(rr <= n && cur <= k) {41 if(a[rr] == 0) {42 if(cur == k) break;43 cur++;44 }45 rr++;46 }47 if(rr - ll > ans) {48 ans = rr - ll;49 al = ll;50 ar = rr - 1;51 }52 while(ll <= rr && a[ll] == 1) ll++;53 cur--;54 ll++;55 }56 printf("%d\n", ans);57 for(int i = 1; i <= n; i++) {58 if(i >= al && i <= ar) printf("1 ");59 else printf("%d ", a[i]);60 }61 printf("\n");62 }63 return 0;64 }