На выборах с мгновенным вторым туром каждый избиратель ранжирует всех кандидатов. Подсчёт идёт раундами:
- Каждый бюллетень отдаёт один голос тому кандидату, который стоит в нём выше всех из ещё не выбывших.
- Если у кандидата больше половины всех бюллетеней, он побеждает.
- Иначе, если у всех оставшихся кандидатов одинаковое число голосов, между ними ничья, и выборы заканчиваются.
- Иначе выбывают все оставшиеся кандидаты с наименьшим числом голосов (все сразу, если таких несколько), и начинается новый раунд.
Реализуйте runoff_election(candidates, ballots).
Входные данные
candidates: имена кандидатов. Кандидат i - это candidates[i].
ballots: по одной строке на избирателя: номера кандидатов (с 0) от самого предпочтительного к наименее предпочтительному. В каждой строке каждый кандидат встречается ровно один раз.
Выходные данные
Верните список с именем победителя или, если выборы закончились ничьей, имена всех кандидатов с равным результатом в том порядке, в котором они идут в candidates. Если бюллетеней нет, ничья между всеми кандидатами.
Ограничения
1 ≤ длина candidates ≤ 9
0 ≤ количество бюллетеней ≤ 200
Примеры
Ввод:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
[0, 1, 2],
[0, 2, 1],
[1, 2, 0],
[1, 0, 2],
[2, 0, 1]
]
Ожидаемый вывод:
expected = ["Ana"]
Ввод:
std::vector<std::string> candidates = {"Ana", "Bo", "Cy"};
std::vector<std::vector<long long>> ballots = {
{0, 1, 2},
{0, 2, 1},
{1, 2, 0},
{1, 0, 2},
{2, 0, 1}
};
Ожидаемый вывод:
std::vector<std::string> expected = {"Ana"};
Ввод:
string[] candidates = new string[] {"Ana", "Bo", "Cy"};
long[][] ballots = new long[][] {
new long[] {0, 1, 2},
new long[] {0, 2, 1},
new long[] {1, 2, 0},
new long[] {1, 0, 2},
new long[] {2, 0, 1}
};
Ожидаемый вывод:
string[] expected = new string[] {"Ana"};
Пояснение
Раунд 1: Ana 2, Bo 2, Cy 1; больше 2,5 голоса ни у кого нет, поэтому Cy выбывает. Бюллетень Cy переходит к Ana, и она побеждает с 3 голосами из 5: ["Ana"].
Ввод:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
[0, 1, 2],
[0, 1, 2],
[1, 2, 0],
[1, 2, 0],
[2, 1, 0],
[2, 1, 0]
]
Ожидаемый вывод:
expected = ["Ana", "Bo", "Cy"]
Ввод:
std::vector<std::string> candidates = {"Ana", "Bo", "Cy"};
std::vector<std::vector<long long>> ballots = {
{0, 1, 2},
{0, 1, 2},
{1, 2, 0},
{1, 2, 0},
{2, 1, 0},
{2, 1, 0}
};
Ожидаемый вывод:
std::vector<std::string> expected = {"Ana", "Bo", "Cy"};
Ввод:
string[] candidates = new string[] {"Ana", "Bo", "Cy"};
long[][] ballots = new long[][] {
new long[] {0, 1, 2},
new long[] {0, 1, 2},
new long[] {1, 2, 0},
new long[] {1, 2, 0},
new long[] {2, 1, 0},
new long[] {2, 1, 0}
};
Ожидаемый вывод:
string[] expected = new string[] {"Ana", "Bo", "Cy"};
Пояснение
У каждого кандидата 2 первых места из 6, поэтому между всеми тремя ничья: ["Ana", "Bo", "Cy"].
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Храните список true/false, кто ещё участвует, и в каждом раунде пересчитывайте голоса заново.
Подсказка 2
Большинство означает, что число голосов × 2 больше числа бюллетеней.
Подсказка 3
Ищите наименьшее число голосов только среди оставшихся кандидатов; если оно у всех оставшихся, это ничья.
Ожидаемая сложность
время O(c^2 × b), доп. память O(c)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.