G - Occupy the Cities

题目

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

思路

二分答案，当这个0到最近的1距离dist+1<=mid时肯定肯定可以，dist+1>mid一定不行。当dist == mid时，正好是个临界值，在这个0左边或者右边的0只有两种情况，要么一定可以，要么一定不可以，dist==mid需要考虑是左边1还是右边1扩展而来，这个时候就要开个vis记录，如果左边1用过了 只能用右边，如果左边用过且右边恰好不满足，那么这个mid不可取。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 10;
const int inf = 0x3f3f3f3f;
int n, lt[N], rt[N];
string s;
// 类似于砍树的问题啊
bool check(int mid)
{
map<int, int> use; // 判断当前的点是不是被首先使用了
// 如果左右都不行那就false了
for (int i = 1; i <= n; i++)
{
if (s[i] == '0')
{
int minn = min(i - lt[i], rt[i] - i) + 1;
if (minn <= mid)
continue;
// 最大情况
这时候优先选取左边
if (minn - 1 == mid)
{
if (lt[i] >= 1 && !use[lt[i]])
{
use[lt[i]] = 1;
continue;
}
if (rt[i] <= n && !use[rt[i]])
{
use[rt[i]] = 1;
continue;
}
}
return false;
}
}
return true;
}
void solve()
{
cin >> n >> s;
s = "@" + s;
// 正反处理0前后1的距离
int pre = -inf;
for (int i = 1; i <= n; i++)
{
if (s[i] == '0')
{
lt[i] = pre;
}
else
pre = i;
}
pre = inf;
for (int i = n; i >= 1; i--)
{
if (s[i] == '0')
{
rt[i] = pre;
}
else
pre = 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;
}
int main()
{
int T;
cin >> T;
while (T--)
{
solve();
}
return 0;
}

最后

以上就是雪白翅膀为你收集整理的【The 2021 CCPC Guilin】G - Occupy the CitiesG - Occupy the Cities的全部内容，希望文章能够帮你解决【The 2021 CCPC Guilin】G - Occupy the CitiesG - Occupy the Cities所遇到的程序开发问题。

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