思路：贪心

贪心思想：一定是将0尽可能移动到字符串的开头

首先，我们需要遍历字符串中的每个字符。对于每个字符，如果它是'1'，我们就增加一个计数器，表示在这个'0'之前有多少个'1'。

当我们遇到一个'0'时，我们需要决定这个'0'应该向前移动多少步。这个步数是当前计数器的值和$k$中的最小值，因为我们不能移动超过k步。

然后，我们交换这个'0'和它前面的'1'，并且减少k的值。如果$k$变为0，我们就可以停止操作，因为我们已经不能再进行更多的操作了。

代码

C++

#include <bits/stdc++.h>
using namespace std;

int n, k;
int a[100010];
int cnt[100010];
string s;
int main()
{
	cin >> n >> k >> s;
	for(int i = 0 ; i < n ; i ++) {
		a[i+1] = s[i] == '1';
		cnt[i+1] = cnt[i] + a[i+1];
	}
	deque<int> que;
	stack<int> ans;
	for(int i = 1 ; i <= n ; i ++) {
		if(a[i] == 1) {
			que.push_back(1);
		}
		else if(k >= cnt[i]) {
			k -= cnt[i];
			que.push_front(0);
		} else {
			for(int j = n ; j > i ; j --) {
				ans.push(a[j]);
			}
			while(k--) {
				ans.push(que.back());
				que.pop_back();
			}
			ans.push(0);
			break;
		}
	}
	while(que.size()) {
		ans.push(que.back());
		que.pop_back();
	}
	while(ans.size()) {
		cout << ans.top();
		ans.pop();
	}
}

Java

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        String str = sc.next();
        StringBuilder ans = new StringBuilder();
        int cnt = 0;		//记录1的数量
        for(int i = 0 ; i < str.length() ; i ++) {
            if(str.charAt(i) == '1') {
                cnt ++;
            } else {		//如果当前是0
                if(k >= cnt) {		//如果足够移到所有1的前面，就移过去
                    k -= cnt;
                    ans.append("0");
                } else {//否则说明k不够用了，就将当前的0往前移k位，也就是将剩余的cnt-k个1放入ans，再当前位的0放进去，再将剩余的k个1放进去，就相当于0往前移k位。
                    ans.append("1".repeat(cnt - k));
                    ans.append("0");
                    ans.append("1".repeat(k));
                    ans.append(str.substring(i+1));		//此时直接将后面剩余的所有字符都存入ans中并结束循环
                    cnt = 0;	//将cnt置为0，防止之后更新
                    break;
                }
            }
        }
        while(cnt-- > 0) {		//在k足够大的情况里不会在for循环内部结束，所以需要手动将1放入ans
            ans.append("1");
        }
        System.out.println(ans);
    }
}

Python

import sys
input = lambda: sys.stdin.readline().strip()

n,k = map(int, input().split())
s = list(input())
left = 0
while left < n and k > 0:
    if s[left] == '0':
        tmp = left
        while tmp != 0 and k > 0 and s[tmp -1] == '1':
            s[tmp], s[tmp - 1] = s[tmp -1], s[tmp]
            k -= 1
            tmp -= 1
    left += 1
print("".join(s))

题目内容

小红有一个01字符串。他认为字典序小的字符串，才是好字符串。所以，他想将这个字符串的字典序变到最小。

小红只能进行最多$k$次操作，每次可以交换任意两个相邻的字符。

小红很忙，于是他找到了准备秋招的你，相信这对你来说一定小菜一碟。

输入描述

一行两个整数$n$和$k$，表示字符串的长度和可以操作的次数。

接下来一行一个长度为$n$的01字符串。

$1\le n\le10^5$

$1\le k\le10^9$

输出描述

字典序最小的字符串

样例

输入

3 1
101

输出

011