pro.algorithms
Здравствуйте, по какому алгоритму решать эту задачу? Покраска забора Сегодня Евгений
решил заняться покраской забора вокруг своего дома. Забор деревянный и состоит из N досок, причем каждая из них имеет ровно две соседние доски: 1 и N доска являются соседними.
Для того, чтобы покраска не стала рутинным занятием, Евгений решил красить доски не по порядку. За сегодня он планирует покрасить лишь Q досок, i-й из которых будет покрашена ai доска.
После покраски очередной доски Евгений хочет определять количество непрерывных участков, состоящих только из непокрашенных досок. Причем, если две непокрашенные доски являются соседними, то они обязательно относятся к одному участку.
Требуется написать программу, которая по действиям Евгения определит количество непокрашенных участков после покраски очередной доски.
2 ответов
Хранить в сете все непокрашенные участки (изначально будет только один - (1, n)), при запросе покраски смотреть, к какому участку относится эта доска и обновлять сет. Нетрудно показать, что после любой операции количество непокрашенных участков изменится не больше, чем на 1, поэтому асимптотика будет равна O(Q log Q)
Хранить в сете все непокрашенные участки (изначаль...
Можно за O(n) решить. Если сначала завести массив длины n. И потом за константу красить каждую доску
Похожие вопросы
Обсуждают сегодня