算法1
(前缀和+双指针) O(n)
//思路:前缀和+双指针
//易知0一定是连续着加的,所以可以先将a[i]==0的下标单独放进一个数组中,然后利用尺取法+双指针处理
//统计数量的优化可以用前缀和–s[j]-s[i-1]即为区间[i,j]中1的数量
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int n,k;
int a[300010];
int s[300010];
vector<int> v;
int ans;
int main()
{
cin>>n>>k;
//注意这里及后面,要把0和n+1放进去,因为双指针的位置是不会放1的,这样的话会有边界问题,所以默认a[0]=a[n+1]=0,更好处理
v.push_back(0);
a[0]=0;
s[0]=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]==0) v.push_back(i);
s[i]=s[i-1]+a[i];
}
if(v.size()-1<=k)//0的个数小于k,直接全输出1即可
{
cout<<n<<endl;
for(int i=1;i<=n;i++) cout<<1<<' ';
return 0;
}
//同上
a[n+1]=0;
s[n+1]=s[n];
v.push_back(n+1);
int start=0;//头指针,i为尾指针
int ans=0;
int l,r;//最终的最大连续区间的左右端点
for(int i=k+1;i<v.size();i++)
{
int beg=v[start];
int fin=v[i];
int num=k+s[fin]-s[beg-1];
if(num>ans)
{
ans=num;
r=v[i-1];
l=v[start+1];
}
start++;
}
cout<<ans<<endl;
for(int i=1;i<=n;i++)
{
if(l<=i&&i<=r) cout<<1<<' ';
else cout<<a[i]<<' ';
}
return 0;
}
算法2
(二分+前缀和) O(nlogn)
//思路:枚举最大连续区间的长度,看里面的0的数量是否<=k,是则可以,统计并更新答案
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int n,k;
int a[300010];
int s[300010];
//vector<int> v;
int ans;
int L,R;
bool check(int x)
{
int start=0;
for(int i=x;i<=n;i++)
{
int num1=s[i]-s[start];//a[1~x]中1的数量
if(x-num1<=k)
{
L=start+1;
R=i;
return true;
}
start++;
}
return false;
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
s[i]=s[i-1]+a[i];
}
int l=0,r=n+1;//二分区间长度
while(l+1<r)
{
int mid=l+r>>1;
if(check(mid)) l=mid;
else r=mid;
}
cout<<l<<endl;
for(int i=1;i<=n;i++)
{
if(L<=i&&i<=R) cout<<1<<' ';
else cout<<a[i]<<' ';
}
return 0;
}