CCPC桂林 - G. Occupy the Cities —— 二分答案

题目来源

题意：

给定一个长度为 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的距离 + 1
if(mina <= mid) continue; //不管方向都能在mid次操作内扩展
if(pre[i] >= 1 && !f[pre[i]] && i-pre[i] <= mid){f[pre[i]] = 1; continue;} //优先标记左边的1
else 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;
}

经验：

整理完之后，发现之前应该做过这样的题目，尽量使用左边的，把右边的留给别人。但是在场上并没有想到二分答案，如果想到了，能不能做出来呢？
同时，碰见这样的题为什么想不到二分答案呢？

这是需要注意的问题。

最后

以上就是清新月饼为你收集整理的CCPC桂林 - G. Occupy the Cities —— 二分答案的全部内容，希望文章能够帮你解决CCPC桂林 - G. Occupy the Cities —— 二分答案所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。