โจทย์
วิธี Ranked Pairs เลือกผู้ชนะโดยพิจารณาการแข่งขันแบบตัวต่อตัวทุกคู่ ผู้มีสิทธิ์ทุกคนจะเรียงลำดับผู้สมัครทุกคน และผู้สมัคร a ชนะผู้สมัคร b เมื่อจำนวนคนที่จัดให้ a อยู่เหนือ b มีมากกว่าจำนวนคนที่จัดให้ b อยู่เหนือ a ส่วนต่างของชัยชนะนั้นคือ (จำนวนคนที่ชอบ a มากกว่า) − (จำนวนคนที่ชอบ b มากกว่า) คู่ที่ทั้งสองฝ่ายได้จำนวนเท่ากันจะไม่ถูกนำมาพิจารณา
- เรียงชัยชนะตามส่วนต่างจากมากไปน้อย ถ้าส่วนต่างเท่ากัน ให้เรียงตามหมายเลขของผู้ชนะจากน้อยไปมาก แล้วจึงเรียงตามหมายเลขของผู้แพ้จากน้อยไปมาก
- ไล่ดูชัยชนะตามลำดับนั้น แล้วล็อกแต่ละรายการเป็นลูกศรจากผู้ชนะไปยังผู้แพ้ เว้นแต่ลูกศรนั้นจะทำให้เกิดวงวนกับลูกศรที่ล็อกไว้แล้ว (กล่าวคือ ผู้แพ้สามารถไปถึงผู้ชนะได้อยู่แล้วโดยเดินตามลูกศรที่ล็อกไว้) ชัยชนะแบบนั้นให้ข้ามไป
- ผู้ชนะคือผู้สมัครที่ไม่มีลูกศรที่ล็อกไว้ชี้มาหาเลย
จงเขียน ranked_pairs_winner(candidates, ballots)
อินพุต
candidates: ชื่อผู้สมัคร ผู้สมัครหมายเลข i คือ candidates[i]
ballots: หนึ่งแถวต่อผู้มีสิทธิ์หนึ่งคน แต่ละแถวเป็นหมายเลขผู้สมัคร (เริ่มนับจาก 0) เรียงจากคนที่ชอบมากที่สุดไปน้อยที่สุด และมีผู้สมัครทุกคนอยู่ครบคนละหนึ่งครั้งพอดี
เอาต์พุต
คืนค่าชื่อผู้สมัครทุกคนที่ไม่มีลูกศรที่ล็อกไว้ชี้มาหา เรียงตามลำดับที่ปรากฏใน candidates โดยปกติจะมีเพียงชื่อเดียว แต่อาจมีหลายชื่อได้เมื่อบางคู่เสมอกัน และถ้าไม่มีบัตรเลยจะได้ผู้สมัครทุกคน
เงื่อนไข
1 ≤ ความยาวของ candidates ≤ 9
0 ≤ จำนวนบัตร ≤ 200
ตัวอย่าง
อินพุต:
candidates = ["Ann", "Bob", "Cal"]
ballots = [
[0, 1, 2],
[0, 1, 2],
[0, 1, 2],
[1, 2, 0],
[1, 2, 0],
[2, 0, 1],
[2, 0, 1],
[2, 0, 1],
[2, 0, 1]
]
ผลลัพธ์ที่คาดหวัง:
expected = ["Cal"]
อินพุต:
std::vector<std::string> candidates = {"Ann", "Bob", "Cal"};
std::vector<std::vector<long long>> ballots = {
{0, 1, 2},
{0, 1, 2},
{0, 1, 2},
{1, 2, 0},
{1, 2, 0},
{2, 0, 1},
{2, 0, 1},
{2, 0, 1},
{2, 0, 1}
};
ผลลัพธ์ที่คาดหวัง:
std::vector<std::string> expected = {"Cal"};
อินพุต:
string[] candidates = new string[] {"Ann", "Bob", "Cal"};
long[][] ballots = new long[][] {
new long[] {0, 1, 2},
new long[] {0, 1, 2},
new long[] {0, 1, 2},
new long[] {1, 2, 0},
new long[] {1, 2, 0},
new long[] {2, 0, 1},
new long[] {2, 0, 1},
new long[] {2, 0, 1},
new long[] {2, 0, 1}
};
ผลลัพธ์ที่คาดหวัง:
string[] expected = new string[] {"Cal"};
คำอธิบาย
Cal ชนะ Ann 6 ต่อ 3 (ส่วนต่าง 3) Ann ชนะ Bob 7 ต่อ 2 (ส่วนต่าง 5) และ Bob ชนะ Cal 5 ต่อ 4 (ส่วนต่าง 1) ล็อก Ann เหนือ Bob ก่อน แล้วล็อก Cal เหนือ Ann ส่วน Bob เหนือ Cal จะทำให้เกิดวงวนจึงข้ามไป ไม่มีลูกศรชี้มาที่ Cal ได้ ["Cal"]
อินพุต:
candidates = ["Ann", "Bob"]
ballots = [
[0, 1],
[1, 0]
]
ผลลัพธ์ที่คาดหวัง:
expected = ["Ann", "Bob"]
อินพุต:
std::vector<std::string> candidates = {"Ann", "Bob"};
std::vector<std::vector<long long>> ballots = {
{0, 1},
{1, 0}
};
ผลลัพธ์ที่คาดหวัง:
std::vector<std::string> expected = {"Ann", "Bob"};
อินพุต:
string[] candidates = new string[] {"Ann", "Bob"};
long[][] ballots = new long[][] {
new long[] {0, 1},
new long[] {1, 0}
};
ผลลัพธ์ที่คาดหวัง:
string[] expected = new string[] {"Ann", "Bob"};
คำอธิบาย
Ann กับ Bob เสมอกัน 1 ต่อ 1 จึงไม่มีลูกศรถูกล็อก และต้องคืนค่าทั้งสองคน ได้ ["Ann", "Bob"]
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
ในบัตรแต่ละใบ ผู้สมัครแต่ละคนถูกชอบมากกว่าทุกคนที่อยู่ลำดับหลังจากตน
คำใบ้ 2
ก่อนล็อกลูกศรจากผู้ชนะไปผู้แพ้ ให้ค้นจากผู้แพ้ไปตามลูกศรที่ล็อกไว้ ถ้าไปถึงผู้ชนะได้ ให้ข้ามไป
คำใบ้ 3
ตอนจบ ผู้ชนะคือผู้สมัครที่ไม่มีลูกศรที่ล็อกไว้ชี้เข้ามา
ความซับซ้อนที่คาดหวัง
เวลา O(b × c^2 + c^4), หน่วยความจำเพิ่ม O(c^2)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน