幸運數字 題解｜APCS 2021 年 9 月中高級 第 3 題

前置知識

這題的核心觀察（留下來的永遠是一段連續區間、以及怎麼不用每輪重找最小值）下面會從頭講；要先會的是兩個工具：

  • 前綴和：NTUCPC Guide〈前綴和與差分〉——pre[i] 存「前 \(i\) 個數的總和」，任何一段連續的總和都是兩個 pre 相減，一次 \(O(1)\)。
  • 帶著位置一起排序：用 pair 與 sort——把（數值、原本的位置）綁成一組排序，排完才知道「第 \(k\) 小的數原本在哪裡」；排序本身的來龍去脈見 NTUCPC Guide〈排序演算法〉。

簡潔題意

給 \(n\) 個互不相同的正整數 \(a_1, \ldots, a_n\)。只要還有超過一個數，就找出目前這些數裡的最小值，把它刪掉，並比較它左邊那段和右邊那段的總和：總和大的那段留下、另一段整段丟掉；兩邊一樣大就留右邊；空的那段總和算 \(0\)。重複到只剩一個數，輸出它（\(1 \le n \le 3 \times 10^5\)，\(1 \le a_i \le 10^7\)）。

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

  • 子題組 1（\(50\) 分）：所有數都介於 \(1\) 到 \(n\) 之間（也就是 \(1\) 到 \(n\) 的排列）。
  • 子題組 2（\(50\) 分）：無額外限制。

核心觀察：留下來的永遠是一段連續區間

一開始留下的是整個序列 \([1, n]\)；每一輪刪掉區間裡的最小值 \(a_k\) 之後，留下的不是 \([l, k - 1]\) 就是 \([k + 1, r]\)——還是一段連續區間，而且只會變短。所以整個過程只要維護兩個數 \(l\)、\(r\)（圖 1）。

圖 1：範例 2 每一輪刪掉區間裡的最小值、留總和大的一邊；由小到大掃過數值，不在區間裡的直接跳過

照題意直接模擬是：每一輪掃一遍 \([l, r]\) 找最小值、再掃一遍算兩邊的總和，一輪 \(O(n)\)。亂數排列的區間大約每輪減半，很快就結束；但輸入是遞增的時候，每輪最小值都在最左邊、只刪掉一個數，要跑 \(n\) 輪，\(n = 3 \times 10^5\) 就是 \(4.5 \times 10^{10}\) 次運算，本站實測 \(2\) 分鐘跑不完。兩件事要分別變快：

  1. 兩邊的總和：前綴和。pre[i] = a[1] + ... + a[i]，左段 \([l, k - 1]\) 的總和是 pre[k - 1] - pre[l - 1]、右段 \([k + 1, r]\) 是 pre[r] - pre[k]，各 \(O(1)\)。
  2. 區間裡的最小值：不要每輪重找，改成把所有數值由小到大掃過一遍。掃到某個值時，它要嘛在目前的區間裡——那它就是區間的最小值（比它小的值都已經掃過、處理掉了），要嘛已經不在區間裡——直接跳過。因為區間只會縮小、被丟掉的數不會回來，每個值只需要看一次，整個掃描是 \(O(n)\)。

先拿下 50 分：排列的話，值 \(v\) 就在 pos[v]

子題組 1 保證數值是 \(1\) 到 \(n\) 的排列，「由小到大掃」根本不用排序：讀入時記 pos[a[i]] = i，然後讓 \(v\) 從 \(1\) 跑到 \(n\)，pos[v] 就是下一個候選的最小值在哪裡。

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

const int MAX_N = 300000;
long long a[MAX_N + 1];
long long pre[MAX_N + 1];        // pre[i] = a[1] + ... + a[i]
int pos[MAX_N + 1];              // pos[v] = 數值 v 在第幾個位置

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
        pos[a[i]] = i;                           // 排列：a[i] 一定在 1 ~ n 之間
    }
    int l = 1, r = n;                            // 目前留下的區間 [l, r]
    for (int v = 1; v <= n && l < r; v++) {      // 從小到大，下一個最小值就是 v
        int k = pos[v];
        if (k < l || k > r) continue;            // v 已經不在區間裡：早就被丟掉了
        long long left = pre[k - 1] - pre[l - 1];    // 左段 a[l] ~ a[k-1] 的總和
        long long right = pre[r] - pre[k];           // 右段 a[k+1] ~ a[r] 的總和
        if (left > right) r = k - 1;             // 左邊比較大才留左邊
        else l = k + 1;                          // 右邊比較大、或一樣大，都留右邊
    }
    cout << a[l] << endl;
    return 0;
}

整題 \(O(n)\)。注意 pre 要用 long long：就算只是 \(1\) 到 \(n\) 的排列，總和 \(1 + 2 + \cdots + 300000 \approx 4.5 \times 10^{10}\) 也已經超過 int 的 \(2147483647\)（估算方法見語法書 2.9）。子題組 1 的 \(50\) 分穩穩到手。

這份程式只能用在排列：子題組 2 的數值最大到 \(10^7\)，pos[a[i]] 會寫到陣列外面，結果不是當掉就是亂數。

從 50 分到 100 分：排序把「第 \(v\) 小的在哪」補回來

子題組 2 的數值不再是 \(1\) 到 \(n\)，pos[v] 這一招失效；但我們真正需要的只是「由小到大的順序，以及每個值原本的位置」——把（數值、位置）綁成 pair 排序就有了，其餘一字不改。

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

const int MAX_N = 300000;
long long a[MAX_N + 1];
long long pre[MAX_N + 1];        // pre[i] = a[1] + ... + a[i]

int main() {
    int n;
    cin >> n;
    vector<pair<long long, int>> order;          // (數值, 位置)
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
        order.push_back({a[i], i});
    }
    sort(order.begin(), order.end());            // 照數值由小到大
    int l = 1, r = n;                            // 目前留下的區間 [l, r]
    for (int v = 0; v < n && l < r; v++) {       // 從小到大，下一個最小值就是 order[v]
        int k = order[v].second;
        if (k < l || k > r) continue;            // 已經不在區間裡：早就被丟掉了
        long long left = pre[k - 1] - pre[l - 1];    // 左段 a[l] ~ a[k-1] 的總和
        long long right = pre[r] - pre[k];           // 右段 a[k+1] ~ a[r] 的總和
        if (left > right) r = k - 1;             // 左邊比較大才留左邊
        else l = k + 1;                          // 右邊比較大、或一樣大，都留右邊
    }
    cout << a[l] << endl;
    return 0;
}

排序 \(O(n \log n)\)、掃描 \(O(n)\)，最大測資本站實測 \(0.1\) 秒。總和最多 \(3 \times 10^5 \times 10^7 = 3 \times 10^{12}\)，pre 一樣要 long long。

測過再交：範例沒有「兩邊一樣大」

兩個範例每一輪的左右總和都不相等；沒蓋到的是：只有一個數、兩邊一樣大（題目說留右邊）、左邊比較大、不是排列的小測資（驗排序版）、以及最大的 \(n\) 配最大的數值（驗 long long 和速度）。

輸入 正確輸出 這一筆在測什麼
1／7 7 只有一個數：不刪任何東西直接輸出
4／5 1 2 3 3 刪 \(1\) 之後左邊 \(5\)、右邊 \(2 + 3 = 5\) 一樣大：要留右邊，接著刪 \(2\) 剩 \(3\)
4／9 1 2 3 9 刪 \(1\) 之後左邊 \(9 > 5\)：留左邊，只剩一個數
3／10 30 20 30 不是排列：刪 \(10\) 留右邊 \([30, 20]\)，再刪 \(20\) 留左邊
用程式造：\(n = 300000\)，\(a_i = 9700000 + i\)（遞增） 10000000 最大測資：每輪只刪最左邊一個數，模擬會超時；總和 \(3 \times 10^{12}\) 驗 long long

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

常犯錯誤
  • 兩邊一樣大時留左邊（left >= right）：兩個範例都過，計分測資只掛 \(1\) 筆；自測表第 2 列現形——印 5，正確是 3。
  • 前綴和用 int：兩個範例都過，計分測資掛 \(17\) 筆（連子題組 1 的總和都超過 int）；自測表第 5 列現形。
  • 沒有跳過已經不在區間裡的值（少了 if (k < l || k > r) continue;）：被丟掉的數會被當成最小值再處理一次——範例 2 印 1，正確是 9。
  • 左段的總和把最小值本身也算進去（pre[k] - pre[l - 1]）：兩邊本來一樣大的局面會誤判成左邊大——範例都過，自測表第 2 列印 5。
  • 排列版的 pos[] 硬交到子題組 2：數值到 \(10^7\)、陣列只有 \(n + 1\) 格，計分測資掛 \(7\) 筆。
  • 每輪重掃找最小值的模擬版硬交：遞增、遞減這類測資每輪只刪一個數，計分測資 \(12\) 筆超時。