Изменение местами символов строки в скобках для достижения максимальной глубины строки H
Учитывая целое число H и строку s, которая содержит только символы ( и ) и правильно сформирована (каждая открывающая скобка имеет соответствующую закрывающую скобку, пары скобок правильно вложены), верните целое число, минимально указывающее, сколько скобок вам нужно перевернуть. получить действительную строку, глубина которой не превышает H.
Глубина строки в данном случае — это максимальный уровень вложенности скобок. Например, строка (()(())) имеет глубину, равную 3.
В целом, я думаю, мы можем применить жадный подход — просто перебирать строковые символы и при этом сохранять переменную, в которой хранится текущая глубина строки. Если в какой-то момент оно окажется выше H, измените текущую скобку. Кроме того, в случае, если глубина будет ниже нуля, также переверните символ.
Это код, который я написал, и он работает отлично:
#include <iostream>
#include <vector>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, H;
cin >> n >> H;
string s;
cin >> s;
int depth = 0;
int ans = 0;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '(' && depth == H) {
s[i] = ')';
++ans;
}
else if (s[i] == ')' && depth == 0) {
s[i] = '(';
++ans;
}
if (s[i] == '(')
++depth;
else
--depth;
}
cout << ans;
}
Это была моя интуиция. Но я не могу понять, как я могу быть уверен, что конечная строка (после изменения определенных символов) всегда будет допустимой (круглые скобки вложены правильно и т. д.).
Во-первых, в какой-то момент мы придем к случаю, когда глубина превысит H. Здесь мы переворачиваем открывающую скобку на закрывающую. Предположим, мы сделали это по индексу i (при повторении s). Благодаря этой модификации у нас будет закрывающая скобка, которой в будущем не будет соответствующей скобки (некоторый индекс j где j > i). Может случиться так, что после этого глубина станет ниже нуля (поэтому мы поменяем закрывающую скобку на открывающую), но это не обязательно (и в итоге мы получим недопустимую строку).
На этом мои рассуждения заканчиваются. Для меня это кажется недействительным, но если код работает, значит я что-то пропустил.
Итак, как я могу быть уверен, что после выполнения всех этих операций я получу действительную строку?
Также прочтите В чем проблема с «использованием пространства имен std;»? и, пожалуйста, не делайте карго-культовых вещей вроде «ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);», которые никогда не пройдут проверку кода в любой профессиональной среде и (если вы действительно не знаете, что делаете) просто приведут к ошибкам.
Но я не могу понять, как я могу быть уверен, что окончательная строка (после изменения местами определенных символов) всегда будет допустимой (круглые скобки вложены правильно и т. д.). Запустите тысячи случайных тестовых случаев с известными ответами, а затем сравните ваши ответы. на известные ответы. Вы просите нас стать вашим фаззинговым двигателем
@Someprogrammerdude Это не совсем разумный совет. В случае проблем с большим объемом ввода программы с заданной временной сложностью могут превысить ограничение по времени без этих строк для ускорения ввода. От их удаления нет никакой пользы, хотя я согласен, что отвязывание cin не так уж и необходимо (и cout в любом случае не привязано по умолчанию).
@Unmitigated Я никогда не работал над каким-либо реальным профессиональным программным проектом, где синхронизация потоков ввода/вывода C и C++ когда-либо имела какое-либо значение. Но я работал над базами кода, куда какие-то придурки добавляли такие вещи, как в код ОП, и это вызывало настоящие ошибки, которые стоили реальных денег. Это «конкурентное кодирование», от которого просто нужно избавиться. Конечно, это существует по какой-то причине, и есть (несколько) случаев, когда это может иметь смысл, но это территория экспертов, и это явно не то, где мы находимся в настоящее время.
@JesperJuhl Пока компании задают технические вопросы, которые представляют собой упрощенные вопросы конкурентного программирования, это вряд ли исчезнет. А поскольку это проблема конкурентного программирования, удаление этих строк на самом деле не помогает (и может существенно ухудшить решение).
Это просто, правда. Как только вы достигли открывающейся скобки на глубине H, вам необходимо преобразовать фрагмент строки до соответствующей закрывающей скобки в )()()...()(, поскольку это единственный способ сохранить глубину на уровне H и не глубже. Я думаю, что ваш алгоритм делает именно это, но сформулирован таким образом, что это не делает это очевидным.
@IgorTandetnik "это единственный выход" нет.
Ответы 1
Перефразируя вопрос, я думаю, вы просите доказать правильность вашей программы, а не «написать фаззер», как предлагалось в некоторых комментариях.
Вы можете думать о допустимой строке скобок следующим образом: для вашей строки скобок s длины n мы можем представить ее с помощью последовательности a. Пусть ai = +1, если i-й символ — (, и пусть ai = -1, если i-й символ — ). Теперь, когда s является допустимой последовательностью скобок тогда и только тогда, когда ∑ i=0k ai ≥ 0 для 0 ≤ k < n и что ∑ i=0n-1 ai = 0. (Подробнее см. Каталонское число и путь Дьюка.)
Таким образом, изменение ( на ) эквивалентно изменению +1 на -1. Следовательно, предположим, что вы меняете al = +1 на al = -1 (от ( до )) и am = -1 на am = +1 (от ) до () для некоторого l < m, тогда ∑ i=0k a i будет неизменным для всех k до l и после m. Что касается сумм между l и m, поскольку ваша программа по сути ищет первое m, где сумма ∑ i=0m ai становится отрицательной после того, как вы изменили ( на ) в точке l, они определенно не отрицательны. Следовательно, строка в квадратных скобках, созданная вашей программой, всегда действительна.
Что касается вашего беспокойства: «из-за этой модификации у нас в будущем будет закрывающая скобка, у которой не будет соответствующей скобки» и «может случиться так, что после этого глубина станет ниже нуля», на самом деле это не будет проблемой. Рассмотрим следующий пример:
( ( ( ) ( ) ) )
Ваше решение должно перевернуть жирные скобки, если я хочу, чтобы максимальная глубина была равна 2.
( ( ) ) ( ) ( )
Теперь обратите внимание на жирные скобки ниже, ранее это была пара скобок: ( ( ( ) ( ) ) )
Но самая левая скобка теперь будет выглядеть следующим образом:
( ( ) ) ( ) ( )
Поэтому вам не нужно беспокоиться о том, какие именно скобки соединены в пары, а достаточно лишь о том, чтобы каждая закрывающая скобка была в паре с некоторой открывающей скобкой.
Не связано, но выкиньте первые три строки функций
main. Они всего лишь часть карго-культа , который обычно никогда не используется в реальном мире.