题目链接
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 < 1 0 5 n<10^5 n<105,说明算法的时间复杂度不能超过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;
}