11426. Нулевая строка

Задана двоичная строка s длины n. Вам разрешено выполнять следующие типы операций над строкой s:

· Удалите один любой символ из s и соедините оставшиеся части строки. Например, если мы удалим третий символ s = 1101, строка станет s = 111.

· Переверните все символы s. Например, если мы перевернем все символы s = 1101, получится s = 0010.

Любой тип операции можно использовать произвольное количество раз. Найдите наименьшее количество операций, за которое все символы строки s можно сделать равными 0.

Вход. Первая строка содержит количество тестов t. Каждый тест состоит из нескольких строк.

Первая строка каждого теста содержит целое число n (1 ≤ n ≤ 10⁵) – длину строки. Следующая строка содержит двоичную строку s длины n.

Известно, что s содержит только 0 и 1.

Выход. Для каждого теста выведите в отдельной строке минимальное количество операций, необходимых для того, чтобы все символы строки s сделать равными 0.

Пример входа	Пример выхода
4 2 01 3 101 3 111 4 0000	1 2 1 0

РЕШЕНИЕ

жадные алгоритмы

Анализ алгоритма

Пусть ones – количество единиц, а zeroes – количество нулей во входной строке. Рассмотрим два варианта получения строки из нулевых символов:

· Удалим все символы 1. На это понадобится ones операций;

· Удалим все символы 0. Получится строка, состоящая только из единиц. Перевернем все символы, получим строку из нулей. На это понадобится zeroes + 1 операций;

Поскольку следует минимизировать количество операций, то используем вариант с меньшим числом преобразований. Ответ равен min(ones, zeroes + 1).

Реализация алгоритма

Читаем количество тестов tests.

cin >> tests;

Последовательно обрабатываем тесты. Читаем входные данные для каждого теста.

while (tests--)

{

cin >> n >> s;

Подсчитываем количество единиц ones и zeroes нулей во входной строке s.

ones = zeroes = 0;

for (i = 0; i < s.size(); i++)

if (s[i] == '1') ones++; else zeroes++;

Вычисляем и выводим ответ.

res = min(zeroes + 1, ones);

cout << res << endl;

}