CCPC桂林

编程入门行业动态更新时间:2024-10-07 22:24:23

CCPC桂林

题目来源

题意：

给定一个长度为 n 的 01 数列。对于每轮操作，如果一个位置上为 1，那么其可以将相邻的最多一个位置上的 0 变成 1。
问，将所有 0 都变成 1 至少需要多少轮操作？

分析：

看这道题之前先看一道简单题：

给定一个长度为 n 的 01 数列，对于每轮操作，如果一个位置上为 1，那么其可以将相邻的最多两个位置上的 0 变成 1。
问，将所有0 都变成 1 至少需要多少轮操作？

对于这道题来说，每个 1 可以向左右两个位置扩展，可以用贪心，也可以二分答案。
二分的话，每次 check 判断左右最近的 1 的距离是否不超过mid。

然后回到这题：
这道题与上面那题的区别就是，每个 1 需要向左或者向右延伸一个位置之后，才能向左右两个位置扩展。
所以，对于每个 0 来说，其变成 1 的最小操作轮数为，其左右最近的 1 的距离 dis，或者 dis + 1（如果那个 1 先往另一方向扩展的话）。

二分最少操作次数 mid，check：

对于每个 0 来说：

如果距离其最近的1的距离 + 1 <= mid 的话，那么无论那个 1 先往哪扩展，这个 0 一定能在 mid 次操作后被扩展。
如果距离其最近的1的距离 = mid 的话，那么需要这个1先往其方向扩展才能保证第 mid 次操作将其扩展。
因为是从前往后走，所以如果左右两边的1距离相同的话，优先考虑标记左边的1，把右边的1留给后面。每个1只能先向一个方向扩展，标记方向只能一次。

bool check(int mid)
{for(int i=1;i<=n;i++) f[i] = 0; //初始未标记for(int i=1;i<=n;i++){if(a[i] == '1') continue;int mina = min(i-pre[i], last[i]-i) + 1; //左右两边最近1的距离 + 1if(mina <= mid) continue; //不管方向都能在mid次操作内扩展if(pre[i] >= 1 && !f[pre[i]] && i-pre[i] <= mid){f[pre[i]] = 1; continue;} //优先标记左边的1else if(last[i] <= n && !f[last[i]] && last[i]-i <= mid){f[last[i]] = 1; continue;}else return 0;}return 1; //所有的0都能在mid次操作内被扩展
}

完整Code：

#include<bits/stdc++.h>
using namespace std;const int N = 2000010, mod = 1e9+7;
int T, n, m;
char a[N];
int pre[N], last[N], f[N];bool check(int mid)
{for(int i=1;i<=n;i++) f[i] = 0;for(int i=1;i<=n;i++){if(a[i] == '1') continue;int mina = min(i-pre[i], last[i]-i) + 1;if(mina <= mid) continue;if(pre[i] >= 1 && !f[pre[i]] && i-pre[i] <= mid){f[pre[i]] = 1; continue;}else if(last[i] <= n && !f[last[i]] && last[i]-i <= mid){f[last[i]] = 1; continue;}else return 0;}return 1;
}signed main(){cin >> T;while(T--){cin>>n;cin >> a+1;int x = -1e9;for(int i=1;i<=n;i++){pre[i] = x;if(a[i] == '1') x = i;}x = 1e9;for(int i=n;i>=1;i--){last[i] = x;if(a[i] == '1') x = i;}int l = 0, r = n;while(l < r) { int mid = l+r>>1;if(check(mid)) r = mid;else l = mid+1;}cout << l << endl;}return 0;
}