Problème
Dans un vote alternatif (ou second tour instantané), chaque électeur classe tous les candidats par ordre de préférence. Le dépouillement se fait en plusieurs tours :
- Chaque bulletin compte comme une voix pour le candidat le mieux classé qui est encore en course.
- Si un candidat obtient plus de la moitié de tous les bulletins, il gagne.
- Sinon, si tous les candidats restants ont le même nombre de voix, ils sont tous à égalité et l'élection s'arrête.
- Sinon, tous les candidats restants qui ont le moins de voix sont éliminés (tous en même temps si plusieurs partagent le plus petit score), et un nouveau tour commence.
Implémentez runoff_election(candidates, ballots).
Entrée
candidates : les noms des candidats. Le candidat i est candidates[i].
ballots : une ligne par électeur, contenant les numéros des candidats (à partir de 0) du préféré au moins apprécié. Chaque ligne contient chaque candidat exactement une fois.
Sortie
Renvoyez une liste contenant le nom du gagnant ou, si l'élection se termine sur une égalité, les noms de tous les candidats à égalité dans l'ordre où ils apparaissent dans candidates. Sans aucun bulletin, tous les candidats sont à égalité.
Contraintes
1 ≤ longueur de candidates ≤ 9
0 ≤ nombre de bulletins ≤ 200
Exemples
Entrée :
candidates = ["Ana", "Bo", "Cy"]
ballots = [
[0, 1, 2],
[0, 2, 1],
[1, 2, 0],
[1, 0, 2],
[2, 0, 1]
]
Sortie attendue :
expected = ["Ana"]
Entrée :
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}
};
Sortie attendue :
std::vector<std::string> expected = {"Ana"};
Entrée :
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}
};
Sortie attendue :
string[] expected = new string[] {"Ana"};
Explication
Premier tour : Ana 2, Bo 2, Cy 1 ; personne ne dépasse 2,5, donc Cy est éliminé. Son bulletin passe à Ana, qui gagne avec 3 voix sur 5 : ["Ana"].
Entrée :
candidates = ["Ana", "Bo", "Cy"]
ballots = [
[0, 1, 2],
[0, 1, 2],
[1, 2, 0],
[1, 2, 0],
[2, 1, 0],
[2, 1, 0]
]
Sortie attendue :
expected = ["Ana", "Bo", "Cy"]
Entrée :
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}
};
Sortie attendue :
std::vector<std::string> expected = {"Ana", "Bo", "Cy"};
Entrée :
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}
};
Sortie attendue :
string[] expected = new string[] {"Ana", "Bo", "Cy"};
Explication
Chaque candidat a 2 voix de premier choix sur 6, donc les trois sont à égalité : ["Ana", "Bo", "Cy"].
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Gardez une liste de booléens indiquant qui est encore en course, et recomptez tout depuis zéro à chaque tour.
Indice 2
Une majorité signifie que voix × 2 est supérieur au nombre de bulletins.
Indice 3
Cherchez le plus petit score uniquement parmi les candidats restants ; si tous les restants l'ont, l'élection se termine sur une égalité.
Complexité attendue
temps O(c^2 × b), espace supplémentaire O(c)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.