SDUT 3165 Round Robina：循環淘汰遊戲模擬

題目描述

N 人圍坐，循環輪流操作。每輪 T 次操作，最後操作者淘汰。若剩餘人操作次數相等則結束。輸出最終剩餘人數及共同操作次數。N,T ≤ 100。

模擬邏輯

• 維護每人操作計數 cnt[i]、存活標記。
• 當前指針 cur 指向下一操作者。
• 每輪：走 T 步（跳過已淘汰者），每步 cnt[cur]++，cur = nextAlive(cur)。第 T 步結束時淘汰該人。
• 淘汰後檢查所有存活者 cnt 是否全等，是則結束。
• 下一輪從被淘汰者下一位存活者開始。

C++ 代碼實現

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

struct Player { int cnt = 0; bool alive = true; };

int nextAlive(const vector& p, int cur) {
    int n = p.size();
    do { cur = (cur + 1) % n; } while (!p[cur].alive);
    return cur;
}

int main() {
    int N, T;
    while (cin >> N, N) {
        cin >> T;
        vector p(N);
        int cur = 0, aliveCnt = N;
        while (true) {
            // 一輪 T 步
            for (int step = 1; step <= T; ++step) {
                p[cur].cnt++;
                if (step == T) { // 淘汰
                    p[cur].alive = false;
                    aliveCnt--;
                    break;
                }
                cur = nextAlive(p, cur);
            }
            if (aliveCnt <= 1) break; // 只剩 0 或 1 人
            // 檢查計數是否全等
            int firstCnt = -1;
            bool equal = true;
            for (auto& pl : p) if (pl.alive) {
                if (firstCnt == -1) firstCnt = pl.cnt;
                else if (pl.cnt != firstCnt) { equal = false; break; }
            }
            if (equal) break;
            // 下一輪起始位置：被淘汰者的下一存活者
            cur = nextAlive(p, cur);
        }
        int finalCnt = 0, commonCnt = 0;
        for (auto& pl : p) if (pl.alive) { finalCnt++; commonCnt = pl.cnt; }
        cout << finalCnt << " " << commonCnt << endl;
    }
    return 0;
}

複雜度

• 每輪淘汰 1 人，最多 N 輪。每輪 T 步，總步數 O(NT) ≤ 10^4，模擬極快。