问题描述

小U拥有一个由0和1组成的字符串，她可以进行最多k次操作，每次操作可以交换相邻的两个字符。目标是通过这些操作，使得最终得到的字符串字典序最小。

例如，小U当前有一个字符串 01010，她最多可以进行 2 次相邻字符交换操作。通过这些操作，她可以将字符串调整为 00101，这是可以通过不超过2次操作得到的字典序最小的字符串。

现在，小U想知道，经过最多k次操作后，能够得到的字典序最小的字符串是什么。

测试样例

样例1：

输入：n = 5, k = 2, s = “01010”
输出：‘00101’

样例2：

输入：n = 7, k = 3, s = “1101001”
输出：‘0110101’

样例3：

输入：n = 4, k = 1, s = “1001”
输出：‘0101’

思路

直接贪心即可。在每一步中选择当前能够移动到最左侧的 0，并尽可能地减少所需的交换次数。这类似于在每个位置选择最小可能的字符，使得整体字符串的字典序最小。
具体步骤如下：

• 遍历字符串的每一个位置 i 从左到右。
• 对于每个位置 i，尝试找到在范围 [i, i + k] 内的最左侧的 0。
• 将该 0 移动到位置 i，所需的交换次数为 j - i（其中 j 是 0 的当前位置）。
• 更新剩余的交换次数 k。
• 重复上述步骤，直到遍历完整个字符串或耗尽所有的交换次数 k。

代码

#include <bits/stdc++.h>

using namespace std;

string solution(int n, int k, string s) {
   string s_copy = s;
    for (int i = 0; i < n && k > 0; ++i) {
        if (s_copy[i] == '0') continue; // 0不用交换
        int pos = -1;
        //  寻找在 [i+1, min(n - 1, i + k)] 范围内的第一个 '0'
        for (int j = i + 1; j < n && j <= i + k; ++j) {
            if (s_copy[j] == '0') {
                pos = j;
                break;
            }
        }
        if (pos == -1) continue; 
        for (int j = pos; j > i; --j) {
            swap(s_copy[j], s_copy[j - 1]);
        }
        k -= (pos - i);
    }

    return s_copy;
}

int main() {
    cout << (solution(5, 2, "01010") == "00101") << endl;
    cout << (solution(7, 3, "1101001") == "0110101") << endl;
    cout << (solution(4, 1, "1001") == "0101") << endl;
    return 0;
}