โจทย์ทั้งหมด
ปานกลาง 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

การเลือกตั้งแบบคัดออกทันที (Instant Runoff)

นับคะแนนเลือกตั้งแบบคัดออกทันทีจากบัตรที่เรียงลำดับความชอบ โดยตัดผู้สมัครที่คะแนนน้อยที่สุดออกทีละรอบ

สิ่งที่คุณจะได้เรียนรู้

  • นับบัตรแต่ละใบให้ตัวเลือกอันดับสูงสุดที่ยังเหลืออยู่
  • ตรวจหาผู้ชนะเสียงข้างมากและกรณีที่ทุกคนเสมอกัน
  • คัดผู้สมัครทุกคนที่ได้คะแนนต่ำสุดออก

โจทย์

ในการเลือกตั้งแบบคัดออกทันที ผู้มีสิทธิ์แต่ละคนจะเรียงลำดับผู้สมัครทุกคนตามความชอบ การนับคะแนนทำเป็นรอบ ๆ ดังนี้

  1. บัตรแต่ละใบนับเป็นหนึ่งคะแนนให้ผู้สมัครที่อยู่ลำดับสูงสุดในบัตรนั้นและยังไม่ถูกคัดออก
  2. ถ้าผู้สมัครคนใดได้คะแนนเกินครึ่งหนึ่งของบัตรทั้งหมด ผู้สมัครคนนั้นชนะ
  3. ถ้าไม่ใช่ และผู้สมัครที่เหลืออยู่ทุกคนได้คะแนนเท่ากัน ถือว่าทุกคนเสมอกันและการเลือกตั้งสิ้นสุด
  4. ถ้าไม่ใช่ทั้งสองกรณี ให้คัดผู้สมัครที่เหลืออยู่ซึ่งได้คะแนนน้อยที่สุดออกทุกคน (ถ้ามีหลายคนได้คะแนนต่ำสุดเท่ากัน ให้คัดออกพร้อมกันทั้งหมด) แล้วเริ่มรอบใหม่

จงเขียน runoff_election(candidates, ballots)

อินพุต

candidates: ชื่อผู้สมัคร ผู้สมัครหมายเลข i คือ candidates[i]

ballots: หนึ่งแถวต่อผู้มีสิทธิ์หนึ่งคน แต่ละแถวเป็นหมายเลขผู้สมัคร (เริ่มนับจาก 0) เรียงจากคนที่ชอบมากที่สุดไปน้อยที่สุด และมีผู้สมัครทุกคนอยู่ครบคนละหนึ่งครั้งพอดี

เอาต์พุต

คืนค่าลิสต์ที่มีชื่อผู้ชนะ หรือถ้าการเลือกตั้งจบลงด้วยการเสมอ ให้คืนค่าชื่อผู้สมัครทุกคนที่เสมอกัน เรียงตามลำดับที่ปรากฏใน candidates ถ้าไม่มีบัตรเลย ผู้สมัครทุกคนถือว่าเสมอกัน

เงื่อนไข

1 ≤ ความยาวของ candidates ≤ 9

0 ≤ จำนวนบัตร ≤ 200

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
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"]

ตัวอย่างที่ 2
อินพุต:
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 กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก