Đề bài
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:
- 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.
- Nếu một ứng viên có hơn một nửa tổng số lá phiếu, người đó thắng.
- 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.
- 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ụ
Đầ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"].
Đầ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.