Осталась одна задача первого тура регионального этапа Всероссийской олимпиады школьников по информатике 2009 года, которая ещё не разобрана на этом канале. Давайте закроем и её:
Довольно серьёзная сложность, приличные входные данные и интересная история.
Первое, что необходимо понять, это как среди двух человек выбрать того, кто будет сидеть. Представим двух пассажиров Alice и Bob. Выгодно, чтобы Alice сидела, если выполняется следующее неравенство:
С таким условием работать неудобно, потому что придётся сравнивать всех пассажиров попарно. Но если все слагаемые с Alice собрать в одной стороне, а с Bob - в другой:
Получается приятное неравенство. То есть можно каждого пассажира независимо оценить и на основе этих оценок составить приоритет на посадку: выгоднее посадить тех, у кого разница a и b максимальна.
Второе, что необходимо понять, это как хранить пассажиров. Мы уже знаем, что достаточно знать лишь одно число (разницу), но нам нужны операции "добавить пассажира", "удалить пассажира" и понимание сидит он или стоит.
Предлагаю пойти простым путём и воспользоваться стандартной структурой данных set, а точнее multiset (так как пассажиры могут иметь одинаковый приоритет), а ещё точнее - парой multiset'ов (отдельно для тех кто стоит и сидит). Благодаря раздельному хранению мы сможем точно отслеживать количество сидящих пассажиров, а благодаря упорядоченности данных во множествах быстро проверять надо ли посадить лучшего из стоящих.
Организуем для всего этого класс:
Для множества stand задал компаратор greater, чтобы элементы хранились в порядке убывания, потому что мне нужен доступ к самому большому из них. По условию задачи m - количество сидячих мест в трамвае, а в profit - буду поддерживать текущий уровень удовлетворения, изменяя его при добавлении и удалении пассажиров.
Напишем метод добавления нового пассажира:
Сначала мы его садим, увеличивая профит, но потом делаем проверку, что количество мест достаточно и нет такой ситуации, что пассажиру удобнее стоять. И если что-то из этого не выполняется, то ставим самого неприбыльного с точки зрения удовлетворения пассажира (это, вполне может быть не тот, которого мы добавили).
Процедура удаления немного сложнее, потому что надо сначала найти положение удаляемого пассажира:
Если пассажир сидел, то мы его удалям, уменьшаем профит и проверяем, стоит ли кого-нибудь посадить на его место. Если же пассажир изначально стоял, то просто удаляем его.
Посмотрим на реализацию метода move, который использовали при добавлении и удалении:
Его пришлось сделать шаблонным, так как сигнатуры множеств отличаются. Реализация очень простая: удаляем из from, добавляем в to. Возвращаем значение элемента, который переложили, чтобы можно было пересчитать профит.
Последний метод нашего класса - это получение текущего уровня удовлетворения:
Имея такой класс, достаточно промоделировать действия, описанные во входных данных. Ничего, кроме библиотеки ввода-вывода и set нам не понадобится:
Считаем все входные данные и сформируем из них два множества входящих и выходящих пассажиров. Для каждого из них будем хранить номер остановки и параметры a и b:
Заведём трамвай нужного размера и переменную, в которой будем накапливать удовлетворение (тип long long, чтобы не было переполнения), и пройдёмся по всем остановкам:
Для каждой остановки посадим (и высадим) всех пассажиров, которым это надо, используя сформированные множества и тот факт, что они упорядочены сначала по номеру остановки:
После всех изменений получаем текущий уровень удовлетворения и добавляем его к ответу.
Выводим ответ, и задача решена:
Замечу, что вместо множеств можно было бы использовать кучу (в бинарной куче константа меньше). Для ускорения также можно было обрабатывать пассажиров оптом: сначала всех удалить и добавить, а уже потом делать пересадки.
Предыдущий выпуск: Задача 531. Газон
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.