Редактировать: Я пытался решить проблему spoj. Вот ссылка на проблему: http://spoj.pl/problems/BRCKTSКронштейны с использованием BIT
Я могу представить две возможные структуры данных для решения проблемы с использованием дерева сегментов, а другой - с помощью BIT. Я уже реализовал решение, используя дерево сегментов. Я читал о BIT, но я не могу понять, как сделать определенную вещь с ним (который я уже упоминал ниже)
Я пытаюсь проверить, если скобки сбалансированы в данной строке, содержащей только ( или ). Я использую BIT (двоичное индексированное дерево) для решения проблемы. Ниже приведена следующая процедура:
Я беру массив размером, равным количеству символов в строке. Я назначаю -1 для ) и 1 для ( соответствующим элементам массива.
Кронштейны сбалансированы в строке только в том случае, если выполняются следующие два условия.
- Суммарная сумма всего массива равна нулю.
- Минимальная суммарная сумма не является отрицательной. т. Е. Минимум кумулятивных сумм всех префиксов массива неотрицателен.
Условие проверки 1 с использованием BIT тривиально. Я перед проблемой при проверке состояния 2.
вы выбрали BIT подход или это домашнее задание? –
Существует гораздо более простое решение, использующее стек. Если это домашнее задание, и вы должны использовать BIT, отметьте его как таковой. – IVlad
Вы можете сделать это без BIT, итерации по строке с помощью счетчика. Добавьте 1 для каждого '(', subtract 1 for ')', убедитесь, что счетчик не опускается ниже нуля и проверьте, равен ли он нулю в конце. (Спасибо Mad) –