Матч 388, Подтасовывание голосования (VoteRigging)

Дивизион 2, Уровень 2

В некоторой стране проходят выборы. Вам известно, что за i - ого кандидата будет голосовать votes[i] людей. Но при этом любого избирателя можно перекупить, заплатив ему немного денег. Ваш любимый кандидат имеет нулевой номер. Кандидат выигрывает выборы, если за него проголосует большее количество людей, чем за каждого из остальных. Какое наименьшее количество людей следует перекупить, чтобы нулевой кандидат выиграл выборы?

Класс: VoteRigging

Метод: int minimumVotes(vector<int> votes)

Ограничения: votes содержит от 1 до 50 элементов, 1 £ votes[i] £ 100.

Вход. Массив votes, содержащий информацию о голосах избирателей.

Выход. Наименьшее количество людей, которое следует перекупить для победы нулевого кандидата.

Пример входа

votes

{5, 7, 7}

{10, 10, 10, 10}

{5, 10, 7, 3, 8}

Пример выхода

2

1

4

РЕШЕНИЕ

моделирование

Если за нулевого кандидата готово проголосовать не больше людей, чем, например, за i - ого, то перекупим одного человека, готового проголосовать за i - ого. Процедура перекупки состоит в увеличении значения votes[0] на 1 и уменьшении на 1 значения votes[i]. Будем продолжать описанный процесс перекупки по одному кандидату до тех пор, пока votes[0] не станет больше каждого из votes[i] (1 £ i < votes.size()).

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

class VoteRigging

{

public:

int minimumVotes(vector<int> votes)

{

vector<int>::iterator i;

int temp = votes[0];

while((i = max_element(votes.begin()+1,votes.end())), votes[0] <= *i)

(*i)--, votes[0]++;

return votes[0] - temp;

}

};