AcWing 5559. 摆放棋子
原题链接
中等
作者:
木可柯
,
2024-04-10 01:08:04
,
所有人可见
,
阅读 4
暴力做法
#include <iostream>
using namespace std;
const int N = 3 * 1e5 + 10;
int a[N], b[N], path[N];
bool st[N];
int n, k, len;
int main() {
cin >> n >> k;
for(int i = 1; i <= n; i++)
cin >> a[i];
int cnt = 0, res = 0;
for(int i = 1; i <= n ; i++)
{
//每次枚举的时候都要重新赋值一下数组
for(int i = 1; i <= n; i++)
b[i] = a[i];
//重置一下个数和添加个数
cnt = 0 , len = k;
for(int i = 1; i <= n; i++)
{
//当前为1就++
if(b[i] == 1) {
cnt++;
//当前为0并且添加次数大于1并且当前没有被枚举过
} else if(b[i] == 0 && len && !st[i]) {
len--;
b[i] = 1;
st[i] = true;
cnt++;
//其他情况如被枚举过了或者没有添加次数了就要清空cnt
} else if(){
cnt = 0;
}
//如果当前长度大于之前的长度就要把当前path数组替换一下
if(cnt > res) {
res = cnt;
for(int i = 1; i <= n; i++)
path[i] = b[i];
}
}
}
cout << res << endl;
for(int i = 1; i <= n; i++)
cout << path[i] << " ";
return 0;
}
双指针
#include <iostream>
using namespace std;
const int N = 3 * 1e5 + 10;
int a[N], b[N], path[N];
int n, m;
int w[N];
int main() {
cin >> n >> m;
for(int i = 0; i < n; i++)
cin >> w[i];
int len = 0, r = 0;
for(int i = 0, j = 0, zeros = 0; i < n; i++)
{
//记录0的个数
if(!w[i]) zeros++;
//如果0大于m的话,就要移动j指针,如果w[j]为0的就要减去zeros
while(zeros > m){
if(!w[j]) zeros--;
j++;
}
//计算加了m个棋子的个数
int t = i - j + 1;
//并进行对比
if(t > len) len = t, r = i;
}
//把加了棋子的地方变为1
for(int i = r; i > r - len; i--)
w[i] = 1;
cout << len << endl;
for(int i = 0; i < n; i++)
cout << w[i] << " ";
return 0;
}