Binary String Minimizing - 题解
比赛与标签
比赛: Codeforces Round 598 (Div. 3) 标签: greedy 难度: *1500
题目大意喵~
你好呀，未来的算法大师！(ฅ^•ﻌ•^ฅ)
这道题是这样的呐：我们拿到一个由 '0' 和 '1' 组成的二进制字符串，长度是 n。我们有一种魔法，可以交换任意两个相邻的字符，但这种魔法最多只能用 k 次。
我们的目标是，通过这不超过 k 次的交换，让这个字符串变得“字典序”最小。字典序最小，简单来说，就是让字符串在从左到右比较时，尽可能地小。比如 "010" 就比 "100" 要小，因为它在第一个位置就是 '0'，赢在了起跑线上喵~
我们需要处理 q 个独立的测试用例，每次都给出 n、k 和初始字符串，然后我们要输出操作后能得到的字典序最小的字符串。
贪心思路大揭秘！
要让一个字符串字典序最小，最关键的策略是什么呢？当然是让 '0' 尽可能地排在前面啦！一个 '0' 在字符串的开头，比任何以 '1' 开头的字符串都要小，对吧？
所以，我们的目标就非常明确了：把 '0' 尽可能地往左边移动！ 这听起来就像一个贪心问题，喵~
那么，我们应该优先移动哪个 '0' 呢？当然是最靠左的那个 '0' 啦！
想象一下，我们想把字符串的第 0 位变成 '0'。我们应该选择哪个 '0' 移过去呢？肯定是选择离第 0 位最近的那个 '0'，也就是我们从左到右遇到的第一个 '0'。因为移动它花费的步数最少，最划算的说！
基于这个想法，我们的贪心策略就诞生啦：
我们从左到右扫描，目标是依次填满最终答案字符串的第
0位，第1位，第2位……假设我们现在要决定最终答案的第
p位（p从 0 开始）。我们就在原始字符串中找到下一个还没被我们移动过的、最靠左的 '0'。设它的位置是z_idx。把这个 '0' 从
z_idx移动到p需要多少步呢？很简单，就是z_idx - p步。我们检查一下我们的魔法次数
k还够不够用：- 如果
k >= z_idx - p：太棒了！我们的魔法足够把这个 '0' 一路护送到p位置。我们就把它放过去，然后更新k，让k = k - (z_idx - p)。接着，我们就可以去考虑填满第p+1位了。 - 如果
k < z_idx - p：哎呀，魔法不够了喵... 我们不能把它移动到p位置了。但是，我们不能浪费这k次机会！我们可以用尽这k次魔法，把它向左移动k步。它的新位置就是z_idx - k。移动完之后，k就变成 0 了，我们再也无法移动任何 '0' 了，所以整个过程就结束了。
- 如果
最后怎么组合成答案呢？ 我们在移动 '0' 的时候，可以先在一个新的空字符串里把这些 '0' 放在它们最终的位置上。那些没有被我们移动的 '0' 和所有的 '1'，它们的相对顺序是不会改变的。我们只需要按顺序把它们填到新字符串的剩余空位里就好啦！
这样一步步贪心地把 '0' 往前搬，就能得到字典序最小的结果了，是不是很清晰呐？
代码实现喵~
下面是具体的代码实现，本猫娘已经加上了详细的注释，希望能帮助你理解每一行代码的作用哦~
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>
// 快速 I/O，让程序跑得更快喵~
void fast_io() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
}
// 处理单个测试用例的函数
void solve() {
int n;
long long k;
std::cin >> n >> k;
std::string s;
std::cin >> s;
// 首先，我们把所有 '0' 的初始位置都记下来，方便我们一个一个处理
std::vector<int> zero_indices;
for (int i = 0; i < n; ++i) {
if (s[i] == '0') {
zero_indices.push_back(i);
}
}
// 如果一个 '0' 都没有，那字符串就没法变了，直接输出就好
if (zero_indices.empty()) {
std::cout << s << std::endl;
return;
}
// `ans` 是我们最终要构建的答案字符串，先用空格占位
std::string ans(n, ' ');
// `is_moved` 用来标记某个原始位置的字符是不是一个被我们移动过的 '0'
std::vector<bool> is_moved(n, false);
// `fill_pos` 指示下一个 '0' 应该被移动到哪个目标位置（从左到右）
int fill_pos = 0;
// 贪心开始！遍历我们找到的所有 '0'
for (int z_idx : zero_indices) {
// 如果魔法次数用完了，就不能再移动了
if (k == 0) {
break;
}
// 计算把这个 '0' 从它现在的位置 `z_idx` 移动到目标位置 `fill_pos` 需要的步数
long long dist = z_idx - fill_pos;
if (k >= dist) {
// 魔法足够！可以把它一路送到最前面
k -= dist;
ans[fill_pos] = '0'; // 在目标位置放上 '0'
is_moved[z_idx] = true; // 标记这个 '0' 已经被我们处理过了
fill_pos++; // 下一个 '0' 的目标位置向右移动一位
} else {
// 魔法不够了... 只能尽力移动
// 用完所有 k 次魔法，把它向左移动 k 步
int new_pos = z_idx - k;
ans[new_pos] = '0';
is_moved[z_idx] = true;
k = 0; // 魔法用光啦
break; // 无法再移动任何 '0'，提前结束循环
}
}
// 重建最终字符串
// 剩下的字符（所有的 '1' 和没被移动的 '0'）需要按原相对顺序填入 `ans` 的空位
int s_ptr = 0; // 一个指针，用来遍历原始字符串 `s`
for (int i = 0; i < n; ++i) {
if (ans[i] == ' ') { // 如果 `ans` 的这个位置还是空的
// 就从 `s` 里找下一个没被移动过的字符
while (s_ptr < n && is_moved[s_ptr]) {
s_ptr++;
}
// 把它填到当前的空位里
if (s_ptr < n) {
ans[i] = s[s_ptr];
s_ptr++;
}
}
}
std::cout << ans << std::endl;
}
int main() {
fast_io();
int q;
std::cin >> q;
while (q--) {
solve();
}
return 0;
}复杂度分析时间！
时间复杂度: O(n) 的说。 我们首先遍历一次字符串
s来找到所有 '0' 的位置，这是 O(n)。然后，我们遍历zero_indices这个向量，它的大小最多是n，所以这也是 O(n)。最后，我们重建答案字符串ans，又是一次 O(n) 的遍历。总的来说，每个测试用例的时间复杂度是线性的，O(n) 哦！因为所有测试用例的n的总和有上限，所以这个算法非常高效。空间复杂度: O(n) 的说。 我们需要一个
zero_indices向量来存储 '0' 的位置，在最坏的情况下（全是'0'），它的大小是 O(n)。我们还需要一个ans字符串和一个is_moved布尔向量，它们的大小也都是 O(n)。所以总的空间复杂度是 O(n) 呐。
猫娘的小总结~
这道题是贪心算法的一个经典应用，喵~ 核心思想就是要抓住“字典序最小”这个关键点。
贪心选择性质：想要全局最优（字典序最小），就要做出局部最优选择。这里的局部最优就是每次都用最少的代价，把最靠前的 '0' 移动到最靠前的位置。这个策略能成功，是因为对字符串前缀的优化，比对后缀的优化更重要。
高效实现：我们没有真的去模拟每一次交换，那样太慢了！而是通过计算和规划，直接构建出最终的字符串。这是一个很重要的解题技巧，可以避免不必要的模拟操作。
数据类型注意：题目中的
k最大可以到n^2，而n是10^6，所以k会非常大，必须使用long long来存储，不然会溢出导致错误哦！
希望这篇题解能帮到你！继续加油，算法的世界还有很多有趣的东西等着我们去探索呢！(ゝω・´★)