Task 48. Выборы
UniLecsЗадача(задача с сайта acmp.ru): В одном из государств все решения традиционно принимались простым большинством голосов на общем собрании граждан, которых, к счастью, было не очень много.
Прошла реформа. Ее суть состояла в следующем: с момента введения ее в действие все избиратели острова делились на K групп (необязательно равных по численности). Голосование по любому вопросу теперь следовало проводить отдельно в каждой группе, причем считалось, что группа высказывается "за", если "за" голосует более половины людей в этой группе, а в противном случае считалось, что группа высказывается "против". После проведения голосования в группах подсчитывалось количество групп, высказавшихся "за" и "против", и вопрос решался положительно в том и только том случае, когда групп, высказавшихся "за", оказывалось более половины общего количества групп.
Эта система вначале была с радостью принята жителями острова. Когда первые восторги рассеялись, очевидны стали, однако, некоторые недостатки новой системы. Оказалось, что сторонники партии, предложившей систему, смогли оказать некоторое влияние на формирование групп избирателей. Благодаря этому, они получили возможность проводить некоторые решения, не обладая при этом реальным большинством голосов.
Пусть, например, на острове были сформированы три группы избирателей, численностью в 5, 5 и 7 человек соответственно. Тогда партии достаточно иметь по три сторонника в каждой из первых двух групп, и она сможет провести решение всего 6-ю голосами "за", вместо 9-и, необходимых при общем голосовании.
Входные данные:
Дан массив, ктр содержит K натуральных чисел, которые задают количество избирателей в группах. Население острова не превосходит 30000 человек.
Напишите функцию, которая по заданному разбиению избирателей на группы определит минимальное количество сторонников партии, достаточное для принятия любого решения.
Например,
[ 5, 5, 7 ], Ответ: 6
[ 4, 2, 1, 3, 7 ], Ответ: 5
Идея: решение не такое сложное, нам нужно упорядочить массив кол-ва избирателей в каждом округе по возрастанию.
Мы знаем, что для победы на выборах нам необходимо набрать более половины голосов в каждом округе и победить в более чем половине округов.
Получаем, что для победы с минимальным кол-вом избирателей надо победить в округах с наименьшим кол-вом избирателей.
Так как победить нужно только в половине округов, то и сортировать массив будем только до половины.
Реализация:
https://gist.github.com/unilecs/315492fad13d5aea4e139d86dfd8350f
Тест: