AcWing 5559. 摆放棋子
原题链接
中等
作者:
七曜
,
2024-03-25 16:37:01
,
所有人可见
,
阅读 4
双指针解法
时间复杂度O(n)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
int n, k, a[N];
void solve()
{
int ans = 0, x = -1, y = -1;//x和y用来记录最大连续处端点下标
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> a[i];
int cnt = 0;//记录双指针区间内0的数量
for (int l = 1, r = 1; l <= n; l++)
{
while (r <= n && ((cnt <= k && a[r] == 1) || (cnt < k)))
//当a[r]是1一定往后走,如果是0且cnt小于k则往后走cnt++
{
if (a[r] == 0)cnt++;
r++;
}
if (r - l > ans)
//r处已经不满足循环条件,退出来了,所以是l到r-1这个闭区间符合,长度为(r-1)-l+1
{
ans = r - l;
x = l, y = r ;
}
if (a[l] == 0)cnt--;
}
cout << ans << endl;
for (int i = 1; i <= n; i++)
{
if (i >= x && i < y)cout << 1 << ' ';//求的区间为1
else cout << a[i] << ' ';//其他不变
}
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while (t--)
{
solve();
}
}
一毛一样啊👏👏太好了