В выборах участвуют n кандидатов. Вы выяснили, что за i-го кандидата планируют проголосовать ai человек. Вы хотите, чтобы кандидат с номером 1 победил в выборах (набрал строго больше голосов, чем все остальные кандидаты). За s рублей можно изменить мнение любого одного голосующего. Какое минимальное количество денег придется потратить на избирательную кампанию?
Пусть у нас имеется n кандидатов, у кандидата 1 – a1 голосов, а у остальных – a2, a3, …, an голосов. Наша задача – добиться того, чтобы кандидат 1 набрал строго больше голосов, чем любой другой кандидат. При этом за s рублей можно изменить мнение одного голосующего – то есть перевести голос от любого кандидата к кандидату 1. При таком переводе количество голосов кандидата 1 возрастает на единицу, а у того кандидата, у которого перевели голос, количество голосов уменьшается на единицу.
Шаг 1. Выясняем начальные условия. Пусть кандидат 1 имеет a1 голосов, а для каждого i от 2 до...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
