โจทย์
ในการเลือกตั้งแบบคัดออกทันที ผู้มีสิทธิ์แต่ละคนจะเรียงลำดับผู้สมัครทุกคนตามความชอบ การนับคะแนนทำเป็นรอบ ๆ ดังนี้
- บัตรแต่ละใบนับเป็นหนึ่งคะแนนให้ผู้สมัครที่อยู่ลำดับสูงสุดในบัตรนั้นและยังไม่ถูกคัดออก
- ถ้าผู้สมัครคนใดได้คะแนนเกินครึ่งหนึ่งของบัตรทั้งหมด ผู้สมัครคนนั้นชนะ
- ถ้าไม่ใช่ และผู้สมัครที่เหลืออยู่ทุกคนได้คะแนนเท่ากัน ถือว่าทุกคนเสมอกันและการเลือกตั้งสิ้นสุด
- ถ้าไม่ใช่ทั้งสองกรณี ให้คัดผู้สมัครที่เหลืออยู่ซึ่งได้คะแนนน้อยที่สุดออกทุกคน (ถ้ามีหลายคนได้คะแนนต่ำสุดเท่ากัน ให้คัดออกพร้อมกันทั้งหมด) แล้วเริ่มรอบใหม่
จงเขียน runoff_election(candidates, ballots)
อินพุต
candidates: ชื่อผู้สมัคร ผู้สมัครหมายเลข i คือ candidates[i]
ballots: หนึ่งแถวต่อผู้มีสิทธิ์หนึ่งคน แต่ละแถวเป็นหมายเลขผู้สมัคร (เริ่มนับจาก 0) เรียงจากคนที่ชอบมากที่สุดไปน้อยที่สุด และมีผู้สมัครทุกคนอยู่ครบคนละหนึ่งครั้งพอดี
เอาต์พุต
คืนค่าลิสต์ที่มีชื่อผู้ชนะ หรือถ้าการเลือกตั้งจบลงด้วยการเสมอ ให้คืนค่าชื่อผู้สมัครทุกคนที่เสมอกัน เรียงตามลำดับที่ปรากฏใน candidates ถ้าไม่มีบัตรเลย ผู้สมัครทุกคนถือว่าเสมอกัน
เงื่อนไข
1 ≤ ความยาวของ candidates ≤ 9
0 ≤ จำนวนบัตร ≤ 200
ตัวอย่าง
อินพุต:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
[0, 1, 2],
[0, 2, 1],
[1, 2, 0],
[1, 0, 2],
[2, 0, 1]
]
ผลลัพธ์ที่คาดหวัง:
expected = ["Ana"]
อินพุต:
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}
};
ผลลัพธ์ที่คาดหวัง:
std::vector<std::string> expected = {"Ana"};
อินพุต:
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}
};
ผลลัพธ์ที่คาดหวัง:
string[] expected = new string[] {"Ana"};
คำอธิบาย
รอบที่ 1 Ana ได้ 2, Bo ได้ 2, Cy ได้ 1 ไม่มีใครได้เกิน 2.5 Cy จึงถูกคัดออก บัตรของ Cy ย้ายไปเป็นของ Ana ซึ่งชนะด้วย 3 จาก 5 คะแนน ได้ ["Ana"]
อินพุต:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
[0, 1, 2],
[0, 1, 2],
[1, 2, 0],
[1, 2, 0],
[2, 1, 0],
[2, 1, 0]
]
ผลลัพธ์ที่คาดหวัง:
expected = ["Ana", "Bo", "Cy"]
อินพุต:
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}
};
ผลลัพธ์ที่คาดหวัง:
std::vector<std::string> expected = {"Ana", "Bo", "Cy"};
อินพุต:
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}
};
ผลลัพธ์ที่คาดหวัง:
string[] expected = new string[] {"Ana", "Bo", "Cy"};
คำอธิบาย
ผู้สมัครทุกคนได้คะแนนอันดับหนึ่งคนละ 2 จาก 6 ใบ ทั้งสามคนจึงเสมอกัน ได้ ["Ana", "Bo", "Cy"]
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
เก็บลิสต์ true/false ว่าใครยังอยู่ในการแข่งขัน และนับคะแนนใหม่ตั้งแต่ต้นทุกรอบ
คำใบ้ 2
เสียงข้างมากหมายถึงคะแนน × 2 มากกว่าจำนวนบัตรทั้งหมด
คำใบ้ 3
หาคะแนนต่ำสุดเฉพาะในหมู่ผู้สมัครที่ยังเหลืออยู่ ถ้าทุกคนที่เหลือได้คะแนนเท่านี้ การเลือกตั้งถือว่าเสมอ
ความซับซ้อนที่คาดหวัง
เวลา O(c^2 × b), หน่วยความจำเพิ่ม O(c)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน