Time Limit:1000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u
Description
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.
Sample Input
7 1 1 0 0 1 1 0 1
4 1 0 0 1 1 1 1
10 2 1 0 0 1 0 1 0 1 0 1
5 1 0 0 1 1 1 1 1 0 1
题解：让改变k个数，使序列连续1的个数最大，我们可以求0的前缀和，然后通过二分来找位置；我竟然用暴力超时了好长时间。。。
二分：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
#define mem(x,y) memset(x,y,sizeof(x))
const int MAXN = ;
int num[MAXN];
int a[MAXN];
int L, n, k; int js(int x){
for(int i = ; i + x <= n; i++){
if(num[i + x] - num[i] <= k){
L = i + ;
return true;
}
}
return false;
}
int erfen(int l, int r){
int mid, ans;
while(l <= r){
mid = (l + r) >> ;
if(js(mid)){
ans = mid;
l = mid + ;
}
else
r = mid - ;
}
return ans;
}
int main(){
while(~scanf("%d%d",&n, &k)){
int temp;
memset(num, , sizeof(num));
for(int i = ; i <= n; i++){
scanf("%d", a + i);
num[i] = num[i - ] + (a[i] == );
}
int ans = erfen(,n);
for(int i = L; i < L + ans; i++){
a[i] = ;
}
printf("%d\n", ans);
for(int i = ; i <= n; i++){
if(i != )printf(" ");
printf("%d",a[i]);
}puts("");
}
return ;
}
暴力超时：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
#define mem(x,y) memset(x,y,sizeof(x))
const int MAXN = ;
int num[MAXN];
int pos[MAXN];
int p[MAXN];
int main(){
int n, k;
while(~scanf("%d%d",&n, &k)){
int gg = ;
for(int i = ; i < n; i++){
scanf("%d", num + i);
if(num[i] == )gg = ;
}
if(!gg){
printf("%d\n",k);
for(int i = ; i < k; i++){
if(i)printf(" ");
printf("");
}
for(int i = k; i < n; i++){
if(i)printf(" ");
printf("");
}puts("");
continue;
}
int kg = , ans = , temp = , cnt = , tp = ;
for(int i = ; i < n; i++){
if(kg == && num[i] == ){
temp = ;
kg = ;
cnt = ;
for(int j = i; j < n; j++){ if(num[j] == ){
temp++;
}
else{
if(cnt + > k)break;
pos[cnt++] = j;
temp++;
}
}
int j = i;
while(cnt < k && j > ){
pos[cnt++] = --j;
temp++;
} if(ans < temp){
ans = temp;
tp = cnt;
for(int j = ; j < tp; j++){
p[j] = pos[j];
}
}
}
if(num[i] == )kg = ;
}
for(int i = ; i < tp; i++){
// printf("%d ",p[i]);
num[p[i]] = ;
}//puts("");
printf("%d\n", ans);
for(int i = ; i < n; i++){
if(i)printf(" ");
printf("%d",num[i]);
}
puts("");
}
return ;
}