Для двоичной строки AA пусть f(A)f(A) обозначает ее плохость, определяемую как разность между количеством нулей и количеством присутствующих в ней единиц. То есть, если в строке есть c0c0 нулей и c1c1 единиц, ее неправильность равна |c0−c1||c0−c1|. Например, плохость «0101» равна |1−1|=0|1−1|=0, плохость «100100» равна |2−1|=1|2−1|=1, плохость «11011101» — это |1−3|=2|1−3|=2, а неправильность пустой строки равна |0−0|=0|0−0|=0.

Вам задано целое число NN и двоичная строка SS.

Вы хотите разбить SS на KK непересекающихся подпоследовательностей (некоторые из которых могут быть пустыми), чтобы максимальное количество ошибок среди всех этих KK подпоследовательностей было минимизировано. Найдите это значение.

Формально,

  • Пусть S1,S2,…,SKS1,S2,…,SK — разбиение SS на непересекающиеся подпоследовательности. Каждый символ SS должен появиться в одном из SiSi. Часть SiSi может быть пустой.
  • Затем найдите минимальное значение max(f(S1),f(S2),…,f(SK))max(f(S1),f(S2),…,f(SK )) для всех возможных вариантов S1,S2,…,SKS1,S2,…,SK, удовлетворяющих первому условию.

Формат ввода

  • Первая строка ввода будет содержать одно целое число TT, обозначающее количество тестовых случаев.
  • Описание каждого тестового примера выглядит следующим образом:
  • В первой строке через пробел записаны два целых числа NN и KK.
  • Вторая строка содержит двоичную строку SS длины NN.

Выходной формат

​Для каждого теста выведите минимальное возможное значение максимальной ошибки, когда SS разбит на подпоследовательности KK.

Пример ввода 1

3
7 5
1010100
4 1
1100
6 2
101111

Пример вывода 1

1
0
2

Итак, сначала прочитав вопрос, я подумал, что могу составить пары 0 и 1 вместе, чтобы плохость была равна нулю. Тем не менее, я немного неправильно прочитал вопрос вместо подпоследовательности, я прочитал подстроку, поэтому я выбрал другой подход, но, поскольку это была подпоследовательность, проблема теперь очень проста.

Теперь посчитаем количество нулей и единиц и соединим их все. После спаривания у нас остались либо все нули, либо все единицы.

one = s.count("1")
zero = n-one
temp = abs(one-zero)

Теперь разделим оставшуюся строку на k и выведем ответ.

Код

for _ in range(int(input())):
    n,k = map(int,input().split())
s = input()
one = s.count("1")
    zero = n-one
if zero == one:
        print(0)
    else:
        temp = abs(one-zero)
        if temp%k != 0:
            print((temp//k)+1)
        else:
            print(temp//k)

Ставьте лайки, комментируйте и голосуйте, как считаете.

Спасибо.