Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Runoff Election

Run an instant runoff election on ranked ballots, eliminating the weakest candidates round by round.

Bạn sẽ học được gì

  • Count each ballot for its top remaining choice
  • Detect a majority winner and a full tie
  • Eliminate all candidates with the lowest count

Đề bài

Xem bản dịch

In an instant runoff election, every voter ranks all the candidates. The count goes in rounds:

  1. Each ballot counts as one vote for its highest-ranked candidate who is still in the race.
  2. If a candidate has more than half of all ballots, that candidate wins.
  3. Otherwise, if every remaining candidate has the same number of votes, they are all tied and the election ends.
  4. Otherwise, every remaining candidate with the fewest votes is eliminated (all of them at once if several share the lowest count), and a new round starts.

Implement runoff_election(candidates, ballots).

Input

candidates: The candidates' names. Candidate i is candidates[i].

ballots: One row per voter: the candidate numbers (0-based) from most preferred to least preferred. Each row lists every candidate exactly once.

Output

Return a list with the winner's name, or, if the election ends in a tie, the names of all tied candidates in the order they appear in candidates. With no ballots, all candidates are tied.

Ràng buộc

1 ≤ length of candidates ≤ 9

0 ≤ number of ballots ≤ 200

Ví dụ

Ví dụ 1
Đầu vào:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
    [0, 1, 2],
    [0, 2, 1],
    [1, 2, 0],
    [1, 0, 2],
    [2, 0, 1]
]

Kết quả mong đợi:
expected = ["Ana"]
Đầu vào:
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}
};

Kết quả mong đợi:
std::vector<std::string> expected = {"Ana"};
Đầu vào:
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}
};

Kết quả mong đợi:
string[] expected = new string[] {"Ana"};

Giải thích

Round 1: Ana 2, Bo 2, Cy 1; nobody has more than 2.5, so Cy is out. Cy's ballot moves to Ana, who wins with 3 of 5: ["Ana"].

Ví dụ 2
Đầu vào:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
    [0, 1, 2],
    [0, 1, 2],
    [1, 2, 0],
    [1, 2, 0],
    [2, 1, 0],
    [2, 1, 0]
]

Kết quả mong đợi:
expected = ["Ana", "Bo", "Cy"]
Đầu vào:
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}
};

Kết quả mong đợi:
std::vector<std::string> expected = {"Ana", "Bo", "Cy"};
Đầu vào:
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}
};

Kết quả mong đợi:
string[] expected = new string[] {"Ana", "Bo", "Cy"};

Giải thích

Every candidate has 2 first-place votes out of 6, so the three of them are tied: ["Ana", "Bo", "Cy"].

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Keep a true/false list of who is still in the race and recount from scratch every round.

Gợi ý 2

A majority means votes × 2 greater than the number of ballots.

Gợi ý 3

Find the lowest count among remaining candidates only; if everyone remaining has it, the election is a tie.

Độ phức tạp mong đợi

O(c^2 × b) time, O(c) extra space

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.