题目描述
给定一个 1×n
的方格棋盘。
其中,一些方格上没有棋子(用0表示),一些方格上放有棋子(用1表示)。
现在,你可以挑选棋盘中不超过 k
个空方格,在其中放上棋子。
我们的目标是让棋盘中最长的连续相邻棋子段的长度尽可能大。
连续相邻棋子段:一段棋子连续相邻的排列在一起,中间没有空方格将它们隔开。
输出最长连续相邻棋子段的最大可能长度以及最终的棋盘盘面。
输入格式
第一行包含两个整数 n,k
。
第二行包含 n
个整数 a1,a2,…,an
,其中 ai
用来表示左起第 i
个方格的状态,0
表示方格上没有棋子,1
表示方格上有棋子。
输出格式
第一行输出一个整数,表示最长连续相邻棋子段的最大可能长度。
第二行输出一个可能的最终棋盘盘面。
如果答案不唯一,输出任意合理答案均可。
数据范围
前 6
个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤3×105,0≤k≤n,0≤ai≤1。
输入样例1:
7 1
1 0 0 1 1 0 1
输出样例1:
4
1 0 0 1 1 1 1
输入样例2:
10 2
1 0 0 1 0 1 0 1 0 1
输出样例2:
5
1 0 0 1 1 1 1 1 0 1
算法1
(二分+前缀和) $O(nlogn)$
通过k个操作会得到相邻长度,但是超过最大长度便会不符合,通过这个边界点我们便可知用二分找这个最大长度
如何判断一个长度符不符合:前缀和存储1的个数,len-(sum[j]-sum[i-1])即为0的个数,个数小于k便可以通过操作得到
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 300010;
int shu[N],sum[N];
int n,k;
int z,y;
bool check(int len)
{
for(int i=1;i+len-1<=n;i++)
{
int j=i+len-1;
if(len-(sum[j]-sum[i-1])<=k)
{
z=i,y=j;//记录修改的区间
return true;
}
}
return false;
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>shu[i];
sum[i]=sum[i-1];
if(shu[i]==1)
{
sum[i]++;//前缀和,储存之前有多少个1
}
}
int l=0,r=n;
while(l<r)//二分找出最后一个使check==true的
{
int mid=l+r+1>>1;
if(check(mid))
{
l=mid;
}
else
{
r=mid-1;
}
}
cout<<r<<endl;
for(int i=z;i<=y;i++)
{
shu[i]=1;
}
for(int i=1;i<=n;i++)
{
cout<<shu[i]<<' ';
}
return 0;
}
算法2
(双指针) $O(n)$
用两个指针,使得两个指针区间内的0的数量始终在k以内,然后存储区间最长
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 300010;
int shu[N],sum[N];
int n,k;
int z,y;
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>shu[i];
}
int zero=0;
int len=0;
for(int i=1,j=1;i<=n;i++)
{
if(shu[i]==0)
{
zero++;
}
while(zero>k)
{
if(shu[j]==0)
{
zero--;
}
j++;
}
if(i-j+1>len)
{
z=j,y=i;
len=i-j+1;
}
}
cout<<len<<endl;
for(int i=z;i<=y;i++)
{
shu[i]=1;
}
for(int i=1;i<=n;i++)
{
cout<<shu[i]<<' ';
}
return 0;
}