Output Contest Matches – จับคู่ทีมแข่งขันใน C++

ปัญหา: Output Contest Matches

มีทีม n ทีม (n เป็นกำลังของ 2) เรียงอันดับ 1 ถึง n (1 = แข็งที่สุด)
จับคู่รอบละ: อันดับ 1 กับ n, 2 กับ n-1, ...
ผู้ชนะไปรอบต่อไป จนเหลือ 1 ทีม แสดงผลการจับคู่เป็นสตริงพร้อมวงเล็บ

ตัวอย่าง

n = 4

Round 1: (1,4), (2,3) → [(1,4),(2,3)]
Round 2: ((1,4),(2,3)) → ((1,4),(2,3))

Output: ((1,4),(2,3))

แนวทางแก้ปัญหา: Simulation Round by Round

ขั้นตอน

1. สร้าง vector teams = ["1", "2", ..., "n"]
2. While teams.size() > 1:
   • สร้าง nextRound ว่าง
   • สำหรับ i = 0..teams.size()/2 - 1:
     • pair = "(" + teams[i] + "," + teams[teams.size()-1-i] + ")"
     • Push เข้า nextRound
   • teams = nextRound
3. คืน teams[0]

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string findContestMatch(int n) {
        vector<string> teams;
        for (int i = 1; i <= n; i++)
            teams.push_back(to_string(i));

        while (teams.size() > 1) {
            vector<string> nextRound;
            int m = teams.size();
            for (int i = 0; i < m / 2; i++) {
                nextRound.push_back("(" + teams[i] + "," + teams[m - 1 - i] + ")");
            }
            teams = move(nextRound);
        }
        return teams[0];
    }
};

int main() {
    Solution ob;
    cout << ob.findContestMatch(4);  // ((1,4),(2,3))
    cout << '\n';
    cout << ob.findContestMatch(8);  // (((1,8),(4,5)),((2,7),(3,6)))
    return 0;
}

ตัวอย่าง n = 8

Round 1: (1,8) (2,7) (3,6) (4,5)
Round 2: ((1,8),(4,5)) ((2,7),(3,6))
Round 3: (((1,8),(4,5)),((2,7),(3,6)))

ความซับซ้อน

• เวลา: O(n log n) – แต่ละรอบลดครึ่ง, รวม n + n/2 + n/4 + ... = 2n
• พื้นที่: O(n) – เก็บสตริงทีมนักแข่ง

ข้อสังเกต

• LeetCode 544
• n รับประกันเป็นกำลังของ 2
• String concatenation ใน C++ อาจช้าถ้า n ใหญ่มาก → ใช้ ostringstream หรือ reserve
• โค้ดต้นฉบับใช้ recursion create() – iterative วิธีนี้เข้าใจง่ายกว่า