Метод ранжированных пар выбирает победителя, рассматривая все парные сравнения кандидатов. Каждый избиратель ранжирует всех кандидатов, и кандидат a побеждает кандидата b, если a ставят выше b больше избирателей, чем ставят b выше a. Перевес этой победы равен (число избирателей за a) − (число избирателей за b). Пары, где у обеих сторон поровну, не рассматриваются.
- Отсортируйте победы по перевесу, начиная с наибольшего. При равном перевесе раньше идёт победа с меньшим номером победителя, а затем с меньшим номером проигравшего.
- Пройдите по победам в этом порядке и закрепите каждую как стрелку от победителя к проигравшему, если только эта стрелка не замкнёт цикл с уже закреплёнными стрелками (то есть если проигравший ещё не может дойти до победителя по закреплённым стрелкам). Такая победа пропускается.
- Победителями становятся кандидаты, в которые не входит ни одна закреплённая стрелка.
Реализуйте ranked_pairs_winner(candidates, ballots).
Входные данные
candidates: имена кандидатов. Кандидат i - это candidates[i].
ballots: по одной строке на избирателя: номера кандидатов (с 0) от самого предпочтительного к наименее предпочтительному. В каждой строке каждый кандидат встречается ровно один раз.
Выходные данные
Верните имена всех кандидатов, в которые не входит ни одна закреплённая стрелка, в том порядке, в котором они идут в candidates. Обычно это одно имя; их может быть несколько, если в некоторых парах была ничья, а если бюллетеней нет, это все кандидаты.
Ограничения
1 ≤ длина candidates ≤ 9
0 ≤ количество бюллетеней ≤ 200
Примеры
Ввод:
candidates = ["Ann", "Bob", "Cal"]
ballots = [
[0, 1, 2],
[0, 1, 2],
[0, 1, 2],
[1, 2, 0],
[1, 2, 0],
[2, 0, 1],
[2, 0, 1],
[2, 0, 1],
[2, 0, 1]
]
Ожидаемый вывод:
expected = ["Cal"]
Ввод:
std::vector<std::string> candidates = {"Ann", "Bob", "Cal"};
std::vector<std::vector<long long>> ballots = {
{0, 1, 2},
{0, 1, 2},
{0, 1, 2},
{1, 2, 0},
{1, 2, 0},
{2, 0, 1},
{2, 0, 1},
{2, 0, 1},
{2, 0, 1}
};
Ожидаемый вывод:
std::vector<std::string> expected = {"Cal"};
Ввод:
string[] candidates = new string[] {"Ann", "Bob", "Cal"};
long[][] ballots = new long[][] {
new long[] {0, 1, 2},
new long[] {0, 1, 2},
new long[] {0, 1, 2},
new long[] {1, 2, 0},
new long[] {1, 2, 0},
new long[] {2, 0, 1},
new long[] {2, 0, 1},
new long[] {2, 0, 1},
new long[] {2, 0, 1}
};
Ожидаемый вывод:
string[] expected = new string[] {"Cal"};
Пояснение
Cal побеждает Ann со счётом 6:3 (перевес 3), Ann побеждает Bob 7:2 (перевес 5), а Bob побеждает Cal 5:4 (перевес 1). Закрепляем Ann над Bob, затем Cal над Ann; Bob над Cal замкнул бы цикл, поэтому пропускаем. В Cal не входит ни одна стрелка: ["Cal"].
Ввод:
candidates = ["Ann", "Bob"]
ballots = [
[0, 1],
[1, 0]
]
Ожидаемый вывод:
expected = ["Ann", "Bob"]
Ввод:
std::vector<std::string> candidates = {"Ann", "Bob"};
std::vector<std::vector<long long>> ballots = {
{0, 1},
{1, 0}
};
Ожидаемый вывод:
std::vector<std::string> expected = {"Ann", "Bob"};
Ввод:
string[] candidates = new string[] {"Ann", "Bob"};
long[][] ballots = new long[][] {
new long[] {0, 1},
new long[] {1, 0}
};
Ожидаемый вывод:
string[] expected = new string[] {"Ann", "Bob"};
Пояснение
У Ann и Bob ничья 1:1, поэтому ни одна стрелка не закрепляется и возвращаются оба: ["Ann", "Bob"].
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
В каждом бюллетене кандидат предпочтительнее всех, кто стоит после него.
Подсказка 2
Перед тем как закрепить стрелку от победителя к проигравшему, выполните поиск от проигравшего по закреплённым стрелкам; если дошли до победителя, пропустите эту победу.
Подсказка 3
В конце победитель - это кандидат без входящих закреплённых стрелок.
Ожидаемая сложность
время O(b × c^2 + c^4), доп. память O(c^2)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.