Олимпиадный тренинг

Задача . Бинарная сортировка


Вы решили съездить проведать своего друга из Озерска. Однако на въезде в город вас остановили и попросили решить задачу, чтобы удостовериться, что вы действительно можете проехать на территорию закрытого города.
Бинарная строка это строка, состоящая только из символов 0 и 1. Полицейский дал вам бинарную строку s1s2 ... sn. Нужно отсортировать эту строку (то есть превратить ее в строку вида 00 ... 0011 ... 11) за наименьшее количество операций. За одну операцию вы можете сделать следующее:
• Выбрать произвольный индекс в строке 1 <= i <= n;
• Для всех j >= i поменять значение в j-й позиции на противоположное, то есть если sj = 1, то сделать sj = 0, и наоборот.

Входные данные
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число t (1 <= t <= 104) количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит единственное целое число n (1 <= n <= 105) длину строки.
Вторая строка каждого набора входных данных содержит бинарную строку s длины n.
Гарантируется, что сумма n по всем наборам входных данных не превосходит 2 ·105.

Выходные данные
Для каждого набора входных данных выведите единственное целое число минимальное количество операций, которое потребуется сделать, чтобы отсортировать строку.
 
Примеры
Входные данные Выходные данные
1 6
1
1
2
10
3
101
4
1100
5
11001
6
100010
0
1
2
1
2
3


Замечание
В первом наборе входных данных строка уже отсортирована.
Во втором наборе входных данных можно выбрать i = 1 и после этого s = 01.
В третьем наборе входных данных можно выбрать i = 1 и получить s = 010, а после этого выбрать i = 2. В результате получим s = 001, то есть отсортированную строку.
В шестом наборе входных данных можно на первой итерации выбрать i = 5 и получить s = 100001. Затем выбрать i = 2 тогда s = 111110. Дальше выбираем i = 1, получая отсор-
тированную строку s = 000001.


time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w641
Python1
Комментарий учителя