營火競賽 題解｜APCS 2026 年 11 月中高級 第 1 題

前置知識

這題是照規則模擬，沒有用到特別的演算法。下面兩件事講解時直接當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：

• 複雜度估算：NTUCPC Guide〈複雜度〉；吳邦一《AP325》0.2.3「複雜度估算」（教材 PDF 第 6～10 頁；Python 版第 0 章）——數出最裡層的動作最多做幾次、代入最大的 \(n\)，就知道來不來得及。
• 計數陣列：語法書 6.7 的「計數陣列：統計每個數字出現幾次」、mex 函數——同一個問題要問很多次時，不要每次都把整串掃一遍，先記在陣列裡，資料變動時順手更新。

簡潔題意

\(n\) 個人圍成一圈，順時針編號 \(1 \sim n\)，每個人的左手邊是順時針的下一位（第 \(n\) 人的左手邊是第 \(1\) 人）。第 \(i\) 人屬於第 \(t_i\) 隊，一開始火把全部點燃，滅火器在第 \(1\) 人手上。拿滅火器的人是行動者，每一回合：

1. 行動者從左手邊開始順時針找，跳過火把已熄滅的人和隊友，熄滅第一位「火把點燃、不同隊」的人；
2. 火把點燃的人如果全部同一隊，比賽結束；
3. 否則從行動者的左手邊開始順時針找，把滅火器交給第一位火把點燃的人（隊友也可以）。

輸出熄滅的火把總數與最後剩下的那一隊；\(k = 1\) 時一回合都不比，熄滅數是 \(0\)（\(1 \le k \le n \le 2000\)，每一隊至少一人）。

依正確通過的測試資料筆數給分，其中：

• 子題 1（\(40\) 分）：\(n < 1000\)。
• 子題 2（\(60\) 分）：無額外限制。

照規則模擬：兩次找人都從行動者的左手邊開始

\(n\) 最多 \(2000\)，照規則一回合一回合做就好。用 team[i] 記第 \(i\) 人的隊伍、lit[i] 記第 \(i\) 人的火把還點燃嗎、actor 記行動者。

圓圈上的「下一位」用 i % n + 1 算（編號 \(1 \sim n\)）：\(i < n\) 時就是 \(i + 1\)；\(i = n\) 時 n % n 是 \(0\)，加 \(1\) 繞回第 \(1\) 人。

一回合裡要沿順時針找兩次人，起點一樣、跳過的人不一樣：

• 找目標：從 actor % n + 1 開始，火把熄滅了、或和行動者同隊，就往下一位走——while (!lit[target] || team[target] == team[actor])。比賽還沒結束，代表火把點燃的人裡至少有兩隊，所以繞不到一圈一定找得到人。
• 傳滅火器：一樣從 actor % n + 1 開始，只跳過火把熄滅的人，隊友也能接。剛被熄滅的人這時已經是熄滅的，會被一起跳過。

圖 1 是範例 1 的第 1、3 回合，把圓圈從行動者開始攤成一排。第 1 回合第 1 人跳過隊友第 2 人、熄滅第 3 人；滅火器從第 1 人的左手邊找起，第 2 人火把點燃，就交給他——如果從被熄滅的第 3 人往下找，會交給第 4 人。第 3 回合第 5 人熄滅第 6 人；傳滅火器時第 6 人剛熄滅、跳過，再往下繞回第 1 人。

兩次找人中間，就是第 2 步「判斷結束」。

判斷結束：記住每隊還剩幾個人點燃

結束的條件「火把點燃的人全部同一隊」，換個說法就是「還有人點燃的隊伍只剩一隊」。直接照這句話寫，是每回合把第 \(1\)～\(k\) 隊逐隊檢查：第 \(c\) 隊從第 \(1\) 人掃到第 \(n\) 人，看有沒有人點燃。這樣一回合要 \(O(kn)\)，最多 \(n - 1\) 回合，總共 \(O(kn^2)\)。每人自己一隊（\(t_i = i\)）時，\(n = 999\) 約要掃 \(7.8 \times 10^8\) 次，本站實測不到 \(1\) 秒，子題 1 還來得及；\(n = 2000\) 約要掃 \(6.2 \times 10^9\) 次，本站實測超過 \(4\) 秒，超過時限。

其實不用每回合重數。熄滅一個人，只有他那一隊的人數會少 \(1\)；那一隊的人數減到 \(0\)，還有人點燃的隊伍就少一隊。所以用前置知識的計數陣列記住兩件事：

• teamAlive[c]：第 \(c\) 隊還有幾個人火把點燃，讀入時先數好；
• aliveTeams：還有人點燃的隊伍數，一開始是 \(k\)（每一隊至少一人）。

aliveTeams == 1 就結束，判斷只要一步。迴圈寫成 while (aliveTeams > 1)，第一回合之前就先檢查：\(k = 1\) 時 aliveTeams 一開始就是 \(1\)，迴圈一次都不跑，熄滅數是 \(0\)。結束時 teamAlive[c] > 0 的那一隊就是答案。

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> team(n + 1);                    // team[i]：第 i 人的隊伍
    vector<int> teamAlive(k + 1, 0);            // teamAlive[c]：第 c 隊還有幾個人火把點燃
    for (int i = 1; i <= n; i++) {
        cin >> team[i];
        teamAlive[team[i]]++;
    }
    vector<bool> lit(n + 1, true);              // lit[i]：第 i 人的火把還點燃嗎
    int aliveTeams = k;                         // 還有人火把點燃的隊伍數（每一隊至少一人）
    int extinguished = 0;                       // 熄滅了幾支火把
    int actor = 1;                              // 滅火器一開始在第 1 人手上

    while (aliveTeams > 1) {                    // 第一回合之前就先檢查：k = 1 一回合都不比
        // 1. 找目標：從行動者的左手邊開始，跳過熄滅的人和隊友
        int target = actor % n + 1;
        while (!lit[target] || team[target] == team[actor])
            target = target % n + 1;
        lit[target] = false;
        extinguished++;
        teamAlive[team[target]]--;
        if (teamAlive[team[target]] == 0)       // 他那一隊沒有人點燃了
            aliveTeams--;

        // 2. 只剩一隊：比賽結束，不用再傳
        if (aliveTeams == 1)
            break;

        // 3. 傳滅火器：一樣從行動者的左手邊開始，只跳過熄滅的人（隊友也能接）
        int next = actor % n + 1;
        while (!lit[next])
            next = next % n + 1;
        actor = next;
    }

    int winner = 0;
    for (int c = 1; c <= k; c++)
        if (teamAlive[c] > 0)                   // 只剩這一隊還有人點燃
            winner = c;
    cout << extinguished << ' ' << winner << '\n';
    return 0;
}

每回合兩次找人各最多走一圈（\(n\) 步），最多 \(n - 1\) 回合，總共不超過 \(2n^2 = 8 \times 10^6\) 步，\(O(n^2)\)，離時限還很遠。子題 1 和子題 2 用的是同一份程式。

測過再交：有三種寫法，範例不一定擋得住

兩個範例已經考到大部分規則：交給隊友、中途淘汰一隊、找目標和傳滅火器都要從第 \(n\) 人繞回第 \(1\) 人、贏的不是第 \(1\) 人那一隊。沒蓋到的是 \(k = 1\)（一回合都不比）、人很少的情況，以及 \(n\)、\(k\) 都很大時跑不跑得完。有三種寫法交上去，兩個範例可能全過：用 do-while 先比一回合、把下一位寫成 (i + 1) % n、每回合逐隊檢查——第 1、2、4 列分別抓它們。

四筆都親眼看過正確，這題就穩了。