Codeforces 660C-Hard Process【尺取法练习】

C. Hard Process time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output You are given an array a with n elements. Each element of a is either 0 or 1.

Let’s denote the length of the longest subsegment of consecutive elements in a, consisting of only numbers one, as f(a). You can change no more than k zeroes to ones to maximize f(a).

Input The first line contains two integers n and k (1 ≤ n ≤ 3·105, 0 ≤ k ≤ n) — the number of elements in a and the parameter k.

The second line contains n integers ai (0 ≤ ai ≤ 1) — the elements of a.

Output On the first line print a non-negative integer z — the maximal value of f(a) after no more than k changes of zeroes to ones.

On the second line print n integers aj — the elements of the array a after the changes.

If there are multiple answers, you can print any one of them.

题意：就是给你一串01字符串，然后你可以将其中k个0改成1，让你求最长的由1组成的字符串！

思路：有关区间动态变化的，很容易想到尺取法，但是我还是一直W，说明理解不够深，应用不行，练习太少！！！

参考博文orz

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int num[300000+100];
int main()
{
	int n,k;
	while(scanf("%d%d",&n,&k)!=EOF)
	{
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&num[i]);
		}
		int r=1,l=1,zr=0,ans=0,ansl=1,ansr=0;
		while(r<=n)
		{
			while(r<=n&&zr<=k)
			{
				if(num[r]==0)
				{
					if(zr==k)
					break;
					else
					{
						zr++;
					}
				}
				r++;
			}
			if(r-l>ans)
			{
				ansr=r-1;
				ansl=l;
				ans=r-l;
			}
			while(l<=n&&num[l])
			l++;
			l++,zr--;
		}
		printf("%d\n",ans);
		for(int i=1;i<=n;i++)
		{
			if(i>=ansl&&i<=ansr)
			printf("1 ");
			else
			printf("%d ",num[i]);
		} 
		printf("\n");
	}
	return 0;
}