HNU Round Robin 題解：約瑟夫問題變體 — 循環鏈表模擬

題目大意

N 名玩家圍成圈 (2≤N≤100)，輪流進行遊戲。每輪恰好進行 T 回合 (2≤T≤100)，**完成第 T 回合的玩家被淘汰**。剩餘玩家繼續，從被淘汰者的下一位開始新一輪 T 回合。若某輪結束後，**所有剩餘玩家的回合計數相等**，遊戲結束。輸出剩餘玩家數 p 和共同計數 c。

核心洞見：循環鏈表完美建模

• 玩家按順序排列 → **循環單鏈表**，每節點存 count (回合數) 和 next 指針。
• 每輪 T 步移動 → 指針在鏈表上前進 T-1 次 (因當前節點已算 1 步)。
• 淘汰玩家 → **刪除鏈表節點** (prev->next = cur->next)。
• 檢查結束條件 → 遍歷剩餘鏈表，檢查所有 count 是否相等。

算法流程

1. 建立 N 節點循環鏈表，count 初始化 0。
2. head 指向當前回合起始玩家 (初始為玩家 1)。
3. 循環直到結束：
4. 從 head 開始走 T-1 步到達第 T 回合玩家 cur。沿途每經過一個節點 count++ (含 head)。
5. cur->count++ (完成第 T 回合)。
6. 記錄 cur 為淘汰目標，head = cur->next (下一輪起始)。
7. 從鏈表刪除 cur (需維護 prev 指針或走 N-1 步找前驅)。
8. 遍歷剩餘鏈表檢查所有 count 是否相等。若相等 → 結束，輸出節點數和共同 count。

完整 C 代碼 (AC)

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int count;
    struct Node* next;
} Node;

Node* head;

void build(int n) {
    head = (Node*)malloc(sizeof(Node));
    head->count = 0;
    head->next = head;
    for (int i = 2; i <= n; ++i) {
        Node* p = (Node*)malloc(sizeof(Node));
        p->count = 0;
        p->next = head->next;
        head->next = p;
    }
}

void simulate(int T, int N) {
    int remaining = N;
    while (true) {
        Node* cur = head;
        Node* prev = nullptr;
        // 走 T-1 步找到第 T 回合玩家，沿途 count++
        for (int step = 1; step < T; ++step) {
            cur->count++;
            prev = cur;
            cur = cur->next;
        }
        cur->count++; // 第 T 回合
        
        // 淘汰 cur
        head = cur->next; // 下一輪從下一位開始
        if (prev) prev->next = cur->next;
        else { // cur 是 head，需找前驅 (走 remaining-1 步)
            prev = head;
            while (prev->next != cur) prev = prev->next;
            prev->next = cur->next;
        }
        free(cur);
        remaining--;
        
        // 檢查是否所有 count 相等
        int first = head->count;
        bool equal = true;
        Node* p = head->next;
        while (p != head) {
            if (p->count != first) { equal = false; break; }
            p = p->next;
        }
        if (equal) {
            printf("%d %d\n", remaining, first);
            // 釋放剩餘節點 (可選)
            break;
        }
    }
}

int main() {
    int N, T;
    while (scanf("%d", &N) == 1 && N) {
        scanf("%d", &T);
        build(N);
        simulate(T, N);
    }
    return 0;
}

關鍵實現細節

1. 步數計算**：走 T-1 步到達第 T 回合玩家。head 算第 1 回合，故先 head->count++ 再走 T-1 步。
2. 刪除節點需前驅**：單鏈表刪除需 prev。若 cur == head，需遍歷找前驅 (或維護雙向鏈表/尾指針)。
3. 計數更新時機**：每經過一個玩家 (含起始) 即 count++。第 T 回合玩家也 count++ (共 T 次遞增)。
4. 結束條件檢查**：每輪淘汰後遍歷鏈表比較 count。

複雜度分析

• 時間：每輪 O(N) 遍歷檢查 + O(T) 步進。最多 N 輪 → O(N² + N·T)。N,T≤100 極快。
• 空間：O(N) 鏈表節點。

數學優化視角 (可選)

可推導公式直接計算每輪淘汰位置與計數增量，避免逐步模擬。但 N≤100 下模擬代碼更直觀、不易出錯，工程上優先。

避坑指南

1. 內存洩漏**：淘汰時 free 節點，結束時釋放剩餘 (雖程序結束 OS 會回收)。
2. T=1 特殊情況**：題目保證 T≥2，無需處理。
3. 輸入結束**：單行 0 結束。
4. 樣例驗證**：5 17 → 2 13, 7 10 → 5 3, 90 2 → 45 1。

結語

HNU Round Robin 是約瑟夫問題的計數變體。循環鏈表是其最自然的數據結構映射：**物理結構 (環) + 邏輯操作 (步進、刪除、遍歷) 完美對應問題語義**。在小規模約束下，直接模擬代碼清晰、邏輯直觀、易於調試，是解決此類「循環淘汰/計數」問題的首選方案。掌握循環鏈表的構建、遍歷、刪除操作，是數據結構基本功的核心體現。