Dự đoán thắng cử Dota2 Senate trong C++

Mô tả bài toán

Cho chuỗi senate gồm 'R' (Radiant) và 'D' (Dire). Mỗi vòng, mỗi senador còn quyền vote có thể cấm quyền của 1 senator đối phương. Senator thông minh chơi tối ưu cho phe mình. Dự đoán phe thắng.

Ví dụ: "RDD" → "Dire".

Giải thuật Hàng đợi (Queue)

1. Đưa chỉ số senator 'R' vào queue qR, 'D' vào qD.
2. Lặp khi cả 2 queue không rỗng:
   • So sánh đầu queue: senator có chỉ số nhỏ hơn (vote trước) sẽ cấm senator kia.
   • Senator thắng push lại vào queue với chỉ số +n (vòng sau).
   • Senator thua pop ra (bị cấm).
3. Queue còn lại là phe thắng.

Cài đặt C++

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

class Solution {
public:
    string predictPartyVictory(string senate) {
        queue<int> qR, qD;
        int n = senate.size();
        for (int i = 0; i < n; i++) {
            if (senate[i] == 'R') qR.push(i);
            else qD.push(i);
        }
        while (!qR.empty() && !qD.empty()) {
            int r = qR.front(), d = qD.front();
            qR.pop(); qD.pop();
            if (r < d) qR.push(r + n);
            else qD.push(d + n);
        }
        return qR.empty() ? "Dire" : "Radiant";
    }
};

int main() {
    Solution ob;
    cout << ob.predictPartyVictory("RDD"); // Dire
    return 0;
}

Độ phức tạp

• Thời gian: O(n) (mỗi senator xử lý 1 lần mỗi vòng).
• Không gian: O(n).