Editorial for 人口遷移 (APCS 2020-10 中級)

簡潔題意

\(R\) 列 \(C\) 行的平面，\(-1\) 的格子不是城市，其餘是城市目前的人口（\(0 \sim 100\)）。兩座城市只有共用一條邊才相鄰（上、下、左、右）。每天：每座城市用「這一天開始時」的人口 \(p\) 算出 \(q = \lfloor p / k \rfloor\)，向每一座相鄰城市各遷出 \(q\) 人（出界或 \(-1\) 的方向不遷、也不扣人）；所有遷移同時發生，當天剛收到的人不能馬上再遷。模擬 \(m\) 天，輸出最後人口最少與最多的城市各有幾人（\(1 \le R, C, m \le 50\)、\(4 \le k \le 50\)）。

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

  • 子題組 1（\(20\) 分）：\(R = 1\) 且 \(m = 1\)。
  • 子題組 2（\(30\) 分）：\(R = 1\)。
  • 子題組 3（\(50\) 分）：無額外限制。

先拿下子題組 1、2（50 分）：只有一列，鄰居只有左右

\(R = 1\) 時平面就是一排 \(C\) 個數，一維陣列裝得下（上冊 6.1）；每座城市的鄰居只有「左邊一格」和「右邊一格」。一天要做的事照題目逐條翻譯：

  1. 對每座城市（不是 \(-1\) 的格子）算 q = population[c] / k——整數除法本身就是無條件捨去（上冊 2.6）。
  2. 左邊一格「沒出界而且是城市」就遷 q 人過去：自己減 q、左邊加 q；右邊同理。出界或 \(-1\) 的方向什麼都不做。

關鍵字是同時發生。如果一邊掃一邊直接改 population，掃到第 \(2\) 座城市時它的人口已經包含第 \(1\) 座剛送來的人，算出的 q 就不是「這一天開始時」的了（13.7）。解法是兩張表：population 是這一天開始時的人口、只讀不改；next 先抄一份舊表，所有加減都寫在 next 上；一天結束再把 next 抄回 population。

子題組 1 保證 \(m = 1\)，但把這一天包進 for (day = 0; day < m; day++) 只多一行，子題組 2 的 \(30\) 分就一起拿下。最後掃一遍，在不是 \(-1\) 的格子裡打擂台找最小、最大（上冊 3.9）——最小值的擂主初值要夠大，用 <climits> 的 INT_MAX（上冊 2.3）；\(-1\) 不是人口，不能拿去比。

#include <iostream>
#include <climits>
using namespace std;

const int MAX_C = 50;

int main() {
    int R, C, k, m;
    cin >> R >> C >> k >> m;          // 子題組 1、2 保證 R = 1：只有一列城市
    int population[MAX_C];
    for (int c = 0; c < C; c++) cin >> population[c];

    for (int day = 0; day < m; day++) {
        int next[MAX_C];              // 新的一張表：先抄一份舊表
        for (int c = 0; c < C; c++) next[c] = population[c];
        for (int c = 0; c < C; c++) {
            if (population[c] == -1) continue;            // 不是城市
            int q = population[c] / k;                    // 用「這一天開始時」的人口算
            if (c - 1 >= 0 && population[c - 1] != -1) {  // 左邊是城市：遷 q 人過去
                next[c] -= q;
                next[c - 1] += q;
            }
            if (c + 1 < C && population[c + 1] != -1) {   // 右邊是城市：遷 q 人過去
                next[c] -= q;
                next[c + 1] += q;
            }
        }
        for (int c = 0; c < C; c++) population[c] = next[c];   // 一天結束：新表變成舊表
    }

    int minimum = INT_MAX;
    int maximum = -1;
    for (int c = 0; c < C; c++) {
        if (population[c] == -1) continue;                // -1 不是人口，不參加比較
        if (population[c] < minimum) minimum = population[c];
        if (population[c] > maximum) maximum = population[c];
    }
    cout << minimum << '\n' << maximum << '\n';
    return 0;
}

這份程式交上去，範例（\(2 \times 3\)）和子題組 3 會 WA——這是正常的，逐筆給分之下子題組 1、2 的 \(50\) 分穩穩到手。要自己驗的話，用下面自測表的前兩筆（都是一列）。

從 50 分到 100 分：四個方向打成表、讀舊表寫新表

平面變二維，鄰居從「左右」變成「上下左右」，其餘原封不動：

  • 地圖用巢狀 vector 讀（13.1），-1 照存，之後一句 == -1 就能判斷是不是城市。
  • 四個方向打成 dr[]、dc[] 方向表（13.3），for (d = 0; d < 4; d++) 跑一圈就是枚舉四鄰格（13.6）。每個鄰格先判出界、再判是不是 \(-1\)——順序反了，出界那次就先讀到地圖外面（13.2）。
  • 遷出量先用舊表算好存進 outgoing（它由「這一天開始時」的人口決定），next 從舊表複製開始，加減全寫在 next；一天結束用 swap 把兩張表對調（10.6）——整段程式只讀 population、只改 next。
#include <bits/stdc++.h>
using namespace std;

// 四鄰格的方向表：上、下、左、右
const int dr[4] = {-1, 1, 0, 0};
const int dc[4] = {0, 0, -1, 1};

int main() {
    int R, C, k, m;
    cin >> R >> C >> k >> m;
    vector<vector<int>> population(R, vector<int>(C));
    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++) cin >> population[r][c];

    for (int day = 0; day < m; day++) {
        vector<vector<int>> outgoing(R, vector<int>(C));   // 每座城市今天向每個鄰居遷出多少人
        vector<vector<int>> next = population;             // 新的一張表，從舊表複製開始
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++)
                if (population[r][c] != -1)
                    outgoing[r][c] = population[r][c] / k;

        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (population[r][c] == -1) continue;      // 不是城市
                for (int d = 0; d < 4; d++) {
                    const int nr = r + dr[d];
                    const int nc = c + dc[d];
                    if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;   // 出界不遷
                    if (population[nr][nc] == -1) continue;                 // 鄰格不是城市不遷
                    next[r][c] -= outgoing[r][c];          // 讀舊表 population、寫新表 next
                    next[nr][nc] += outgoing[r][c];
                }
            }
        }
        population.swap(next);                             // 一天結束：新表變成舊表
    }

    int minimum = INT_MAX;
    int maximum = -1;
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            if (population[r][c] == -1) continue;
            minimum = min(minimum, population[r][c]);
            maximum = max(maximum, population[r][c]);
        }
    }
    cout << minimum << '\n' << maximum << '\n';
    return 0;
}

運算量：每天掃 \(R \times C \le 2500\) 格、每格看 \(4\) 個方向，\(m \le 50\) 天總共 \(5 \times 10^5\) 次上下，一秒綽綽有餘。人口不會變負：\(k \ge 4\)、鄰居最多 \(4\) 座，一天最多遷出 \(4 \lfloor p / 4 \rfloor \le p\) 人。

測過再交：範例只有一天，抓不到「只模擬一天」和「斜角當鄰居」

範例是 \(2 \times 3\)、\(m = 1\)，而且只印最少和最多兩個數——很多錯法改變了中間那些城市的人口，卻剛好沒動到最小值和最大值，範例照樣過。自己補幾筆：

輸入 正確輸出 這一筆在測什麼
1 3 4 1 ／ 4 3 0 0 ／ 4 一列、一天：只有 \(4\) 人的城市往右遷 \(1\) 人，子題組 1 版就能驗。就地更新的程式會讓剛收到人的 \(3\) 變成 \(4\)、馬上再往兩邊遷，印 1／4
1 3 4 2 ／ 4 3 0 1 ／ 4 同一筆多跑一天：第二天 \(4\) 人的城市在中間、往左右各遷 \(1\)。只模擬一天的程式印 0／4——範例 \(m = 1\) 抓不到
2 2 50 3 ／ 100 -1 ／ -1 7 7 ／ 100 兩座城市只有斜角相鄰＝沒有鄰居，三天都不動。把斜角當鄰居的程式印 11／96；朝 \(-1\) 的方向也扣人口的程式印 7／92——這兩種錯範例都抓不到
1 1 4 5 ／ 0 0 ／ 0 只有一座 \(0\) 人的城市：最少和最多是同一座

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

常犯錯誤
  • 就地更新（一邊掃一邊改同一張表）：範例印 2／8（該印 2／7）。看到「同時」兩個字，反射動作就是另開一張表。
  • 只模擬一天：範例 \(m = 1\) 照樣過；自測表第 2 列印 0／4。
  • 把斜對角也當相鄰：範例的最少、最多剛好沒被動到，照樣過；自測表第 3 列印 11／96。
  • 朝 \(-1\) 的方向也扣掉 q 人：範例同樣抓不到；自測表第 3 列印 7／92。連出界方向也扣的版本範例印 2／4。
  • 把 q 當成總遷出量再平分給鄰居：題目是向每一座鄰居各遷 q 人——範例印 2／10。
  • \(-1\) 也拿去比最小值：範例印 -1／7。