Автор разбора: Михаил Густокашин

Упорядочим партии  по убыванию количества голосующих (например, это можно сделать с помощью кучи). Теперь рассмотрим следующую подзадачу: сколько будет стоить сманивание людей для победы фиксированной партии.

Решать задачу будем бинарным поиском по уровню отсечения. Уровень отсечения будет обозначать максимальное количество людей, которое может проголосовать за партию, которая не победит на выборах. Минимальный уровень отсечения - 0, максимальный - максимум из количеств голосующих за партии.

Теперь у нас фиксирован уровень отсечения и необходимо научится отвечать на вопрос: победит ли фиксированная партия, если остальные партии обрезать по уровню отсечения и всех обрезанных людей добавить к этой фиксированной партии. Эта задача решается с помощью обычного бинарного поиска. А именно, нам необходимо найти номер первой партии (в упорядоченном массиве), за которую голосует людей меньше, чем уровень отсечения. Теперь мы знаем, сколько партий должно быть обрезано. Быстро подсчитать количество отрезанных людей можно с помощью предварительного подсчета суммы всех голосующих людей за первые K партий. Это делается за линейное время: S(K) = S(K-1) + (количество людей, голосующих за партию K). От этой суммы для последней обрезаемой партии (сколько всего людей голосовало за первые K партий) необходимо отнять произведение количества обрезаемых партий на уровень отсечения (сколько людей стало голосовать за эти партии). Всех отрезанных людей прибавим к результатам исследуемой сейчас партии и, если количество людей, голосующих за нее, оказалось больше, чем уровень обрезания - то такой уровень обрезания дает нам победу. В некоторых случаях результат можно удешевить, а именно, если количество голосующих за нашу партию превышает уровень обрезания больше чем на 2, то часть людей мы сманили зря и можно вернуть их некоторым партиям (т.е. раздаем обрезанным партиям по одному человеку до тех пор, пока уровень нашей партии не будет отличаться от уровня отсечения на 2). Это делается за O(1) - достаточно от количества голосующих за партию отнять уровень отсечения+2. Естественно, больше чем по одному человеку раздавать не имеет смысла - правильный ответ будет достигнут при другом уровне отсечения.

Сложность полученного решения будет такой: O(NlogN) [сортировка] + N [перебор всех партий, которые можно подкупить]*log(MAX)[перебор уровня отсечения]*log(N) [поиск партий, которые попадают под отсечение].

Задана информация об N партиях - количестве голосующих за них и размер взятки, который необходимо дать партии, чтобы она делала что нужно, если победит. Изменение результата голосования одного человека стоит 1 уе. Требуется за наименьшее количество денег подкупить партию и людей так, чтобы она победила.