144. 字典序最小的 01 字符串（卡码网周赛第二十六期（23年阿里淘天笔试真题））

题目链接
144. 字典序最小的 01 字符串（卡码网周赛第二十六期（23年阿里淘天笔试真题））

题目描述

小红有一个 01 字符串，她可以进行最多 k 次提作，每次操作可以交换相邻的两个字符，问可以得到的字典序最小的字符串是什么。

输入

第一行包含两个整数，n（1 < n < 10^5）和 k（1 < k < 10^9），表示字符串的长度和可以进行的操作次数。
接下来一行一个长度为 n 的 01 字符串。

输出

输出一个长度为 n 的字符串，表示字典序最小的字符串。

样例1输入

5 2
01010

样例1输出

00101

样例1解释

数据范围$n<10^5$，说明算法的时间复杂度不能超过O(nlogn)，即不能使用暴力解法

样例2输入

5 10
10000

样例2输出

00001

样例2解释

样例3输入

10 10
1111101100

样例3输出

0110111110

样例3解释

题解1（C++版本）

// 贪心, 左边的0尽可能往前放
#include<bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;
char s[N];int n, k, pos0[N], cnt; // pos0[i]表示从左往右数，第i个字符'0'的下标int main(){scanf("%d%d%s", &n, &k, s + 1);int last = 0; // 用来标记第一个字符'1'的下标for(int i = 1; i <= n; i++){if(s[i] == '0') pos0[++cnt] = i;else if(!last){last = i;}}if(!last || last >= pos0[cnt]){ // 字符串s中没有字符'1'或者所有的字符'1'在任何一个字符'0'的后面printf("%s\n", s+1);return 0;}int i = 1;while(i <= cnt && last > pos0[i]) i++; // 由于要求移动的字典序最小，因此，可以过滤掉第一个1前面的字符'0'，while(k > 0 && i <= cnt && last <= n) {int R0 = pos0[i]; // 当前要移动的字符'0'的下标int L1 = last; // 当前要移动的字符'1'的下标if(R0 - L1 <= k){ // 当前移动（R0 - L1）次后，还可以往下移动，使得最终的字典序更小k -= (R0 - L1);s[R0] = '1'; s[L1] = '0';last++;i++;}else {s[R0] = '1'; s[R0 - k] = '0';k = 0;}while(last <= n && s[last] == '0') last++; // 寻找上一次移动之后的下一个字符'1'的下标}printf("%s\n", s + 1);return 0;
}