贪心思想:一定是将0尽可能移动到字符串的开头
首先,我们需要遍历字符串中的每个字符。对于每个字符,如果它是'1',我们就增加一个计数器,表示在这个'0'之前有多少个'1'。
当我们遇到一个'0'时,我们需要决定这个'0'应该向前移动多少步。这个步数是当前计数器的值和k中的最小值,因为我们不能移动超过k步。
然后,我们交换这个'0'和它前面的'1',并且减少k的值。如果k变为0,我们就可以停止操作,因为我们已经不能再进行更多的操作了。
小红有一个01字符串。他认为字典序小的字符串,才是好字符串。所以,他想将这个字符串的字典序变到最小。
小红只能进行最多k次操作,每次可以交换任意两个相邻的字符。
小红很忙,于是他找到了准备秋招的你,相信这对你来说一定小菜一碟。
一行两个整数n和k,表示字符串的长度和可以操作的次数。
接下来一行一个长度为n的01字符串。
1≤n≤105
1≤k≤109
字典序最小的字符串
输入
3 1
101
输出
011