ทายพรรคชนะใน Dota2 Senate ใน C++

ใน Dota2 มีพรรค 2 พรรค: Radiant (R) และ Dire (D) สมาชิกวอตในรอบๆ โดยแต่ละรอบแต่ละคนทำได้ 1 ใน 2 อย่าง: 1) ไล่ออกคนอื่น (ban) 2) ประกาศชนะถ้าคนที่เหลืออยู่ทุกคนเป็นพรรคเดียวกัน ทุกคนเล่นอย่างเหมาะสมที่สุด ต้องการทายว่าพรรคไหนชนะ

ตัวอย่าง: "RDD" → "Dire" (R ไล่ D ตัวที่ 2, D ตัวที่ 3 ไล่ R ตัวแรก, รอบ 2 เหลือ D เดียว)

ขั้นตอนการแก้ปัญหา (Queue Simulation)

1. สร้างคิว qR และ qD เก็บดัชนีของ R และ D
2. วนจนคิวใดคิวหนึ่งว่าง:
   • ดูหน้าคิวทั้งสอง: ดัชนีน้อยกว่า = ได้เล่นก่อน
   • ผู้เล่นก่อนจะ ban คนอีกพรรค (pop คิวตรงข้าม) และตัวเองไปต่อท้ายคิวของตนเองด้วยดัชนีใหม่ n++
3. คิวไหนเหลือ → พรรคนั้นชนะ

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

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

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

int main() {
    Solution ob;
    cout << ob.predictPartyVictory("RDD");
}

Input

"RDD"

Output

Dire