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

Bầu cử loại dần (Instant Runoff)

Kiểm phiếu theo cách loại dần trên các lá phiếu xếp hạng, loại những ứng viên yếu nhất qua từng vòng.

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

  • Tính mỗi lá phiếu cho lựa chọn cao nhất còn trong cuộc đua
  • Phát hiện người thắng đa số và trường hợp hòa toàn bộ
  • Loại tất cả ứng viên có số phiếu thấp nhất

Đề bài

Xem bản gốc (English)

Trong hình thức bầu cử loại dần tức thì (instant runoff), mỗi cử tri xếp hạng tất cả ứng viên. Việc kiểm phiếu diễn ra theo từng vòng:

  1. Mỗi lá phiếu được tính là một phiếu cho ứng viên được xếp hạng cao nhất trên lá phiếu đó mà vẫn còn trong cuộc đua.
  2. Nếu một ứng viên có hơn một nửa tổng số lá phiếu, người đó thắng.
  3. Nếu không, khi mọi ứng viên còn lại đều có số phiếu bằng nhau, họ cùng hòa và cuộc bầu cử kết thúc.
  4. Nếu không, mọi ứng viên còn lại có ít phiếu nhất đều bị loại (loại cùng lúc nếu nhiều người cùng có số phiếu thấp nhất), rồi bắt đầu vòng mới.

Hãy viết runoff_election(candidates, ballots).

Đầu vào

candidates: Tên các ứng viên. Ứng viên i là candidates[i].

ballots: Mỗi cử tri một hàng, gồm số thứ tự các ứng viên (đánh số từ 0) xếp từ người được ưu tiên nhất đến người ít được ưu tiên nhất. Mỗi hàng liệt kê mọi ứng viên đúng một lần.

Đầu ra

Trả về danh sách gồm tên người thắng, hoặc nếu kết quả hòa thì gồm tên tất cả ứng viên hòa nhau theo thứ tự trong candidates. Nếu không có lá phiếu nào, mọi ứng viên đều hòa.

Ràng buộc

1 ≤ độ dài candidates ≤ 9

0 ≤ số lá phiếu ≤ 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

Vòng 1: Ana 2, Bo 2, Cy 1; không ai vượt quá 2.5 phiếu nên Cy bị loại. Lá phiếu của Cy chuyển sang Ana, và Ana thắng với 3 trên 5 phiếu: ["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

Mỗi ứng viên đều có 2 phiếu xếp hạng nhất trên tổng số 6 phiếu, nên cả ba cùng hòa: ["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

Giữ một danh sách true/false cho biết ai còn trong cuộc đua, và đếm lại từ đầu ở mỗi vòng.

Gợi ý 2

Đạt đa số nghĩa là số phiếu × 2 lớn hơn tổng số lá phiếu.

Gợi ý 3

Chỉ tìm số phiếu thấp nhất trong các ứng viên còn lại; nếu mọi người còn lại đều có số phiếu đó thì cuộc bầu cử hòa.

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

thời gian O(c^2 × b), bộ nhớ phụ O(c)

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.