Лексикографически наименьшая двоичная строка после не более K смежных перестановок - PullRequest
Новая
       26

Лексикографически наименьшая двоичная строка после не более K смежных перестановок

0 голосов
/ 01 декабря 2019

Я пытался задать вопрос о codeforces, но он не прошел тестовый пример 2.

Вопрос:

Вам задана двоичная строка длины n (т.е. строка, состоящая из n символов '0' и '1').

За один ход вы можете поменять местами два соседних символа строки. Какую лексикографически минимальную возможную строку вы можете получить из данной, если можете выполнить не более k ходов? Вполне возможно, что вы вообще не выполняете никаких шагов.

Обратите внимание, что вы можете поменять местами одну и ту же пару смежных символов с индексами i и i + 1 произвольное (возможно, нулевое) число раз. Каждый такой обмен считается отдельным ходом.

Вы должны ответить на q независимых тестовых случаев.

Вход

Первая строка ввода содержитодно целое число q - количество тестовых случаев.

Первая строка тестового примера содержит два целых числа n и k - длину строки и количество ходов, которые вы можете выполнить.

Вторая строка теста содержит одну строку, состоящую из n символов «0» и «1».

Выходные данные

Для каждого теста выведите ответ наit: лексикографически минимально возможная строка длины n, которую вы можете получить из заданной, если вы можете выполнить не более k ходов.

Сайт: 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)
...