Xuất trận đấu thi đấu trong C++

Giới thiệu

Cho n đội (1..n, 1 mạnh nhất). Mỗi vòng pair đội mạnh nhất còn lại với đội yếu nhất còn lại. Trả về chuỗi biểu diễn cặp đấu cuối cùng sau các vòng loại, dùng dấu ngoặc và dấu phẩy.

Thuật toán: Mô phỏng vòng đấu

Duy trì vector chuỗi đại diện cho các "đội" (có thể là cặp đấu đã gộp). Mỗi vòng: tạo vector mới bằng cách pair v[i] với v[size-1-i] cho i = 0..size/2-1, bọc trong ngoặc. Lặp cho đến khi còn 1 phần tử.

Cài đặt C++

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

class Solution {
public:
    string findContestMatch(int n) {
        vector teams;
        for (int i = 1; i <= n; i++) teams.push_back(to_string(i));
        while (teams.size() > 1) {
            vector next;
            for (int i = 0, j = teams.size() - 1; i < j; i++, j--) {
                next.push_back("(" + teams[i] + "," + teams[j] + ")");
            }
            teams = move(next);
        }
        return teams[0];
    }
};

int main() {
    Solution ob;
    cout << ob.findContestMatch(4); // Output: ((1,4),(2,3))
    return 0;
}

Ví dụ n=8

Vòng 1: (1,8) (2,7) (3,6) (4,5)
Vòng 2: ((1,8),(4,5)) ((2,7),(3,6))
Vòng 3: (((1,8),(4,5)),((2,7),(3,6)))

Độ phức tạp

• Thời gian: O(n log n) – mỗi vòng giảm đôi số đội, xử lý O(n) tổng cộng.
• Không gian: O(n) – lưu chuỗi trung gian.

LeetCode 544 "Output Contest Matches".