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解释

题解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; }