在最多K个相邻交换之后,按字典顺序最小的二进制字符串

我尝试了有关代码强制的问题,但未通过测试用例2。

问题是:

您将得到一个长度为n的二进制字符串(即由n个字符“ 0”和“ 1”组成的字符串)。

只需一步即可交换字符串的两个相邻字符。如果最多只能进行k次移动,那么从给定的字符串中可以得到的最小词典顺序字符串是多少?您可能根本不执行任何移动。

请注意,您可以将同一对相邻字符与索引i和i + 1任意(可能为零)次交换。每次这样的交换都被视为单独的举动。

您必须回答q个独立的测试用例。

输入

输入的第一行包含一个整数q-测试用例的数量。

测试用例的第一行包含两个整数n和k —字符串的长度和可以执行的移动次数。

测试用例的第二行包含一个由n个字符“ 0”和“ 1”组成的字符串。

输出

对于每个测试用例,在其上打印答案:如果您最多可以执行k次移动,则可以从给定的字符串中获得最小字串长度为n的字典。

网站:https://codeforces.com/contest/1256/problem/D

我的方法:

我迭代第二个索引中的字符串,每当遇到'10'时,我都会进行交换,然后再次迭代第二个索引。

我的代码:

q = int(input())
for i in range(q):
[n,k] = list(map(int,input().split(" ")))
s = list(map(int,list(input())))
a = 0
j = 1

while(a < k and j < n-1):
    if(s[j] == 1 and s[j+1] == 0):
        s[j] = 0
        s[j+1] =1
        a += 1
        j = 1

    elif(s[j-1] == 1 and s[j] == 0): #This checks the occruence of the pattern '101' which is formed 
        s[j-1] = 0                   # after the swapping of the pattern '110'
        s[j] = 1
        a += 1
        j = 1
    else:
        j += 1

s = list(map(str,s))
s = "".join(s)
print(s)
shuaikai006 回答:在最多K个相邻交换之后,按字典顺序最小的二进制字符串

从语法上来说,最小二进制字符串的左侧为全零。当我们从左侧进行迭代时,我们将零移动到尽可能远的位置,并跟踪左侧有多少个1和可用的掉期数。例如,

11011010,5 swaps

Arrive at first 0:
5 swaps,2 1's
Output 0
swaps = swaps - 2

Arrive at second 0:
3 swaps,2 + 2 = 4 1's
Output 10111
swaps = swaps - 3

No more swaps available,so output the rest of the string:

0 + 10111 + 10 =
01011110
本文链接:https://www.f2er.com/2997649.html

大家都在问