最佳選擇 題解｜APCS 2024 年 6 月高級 第 4 題

前置知識

這題是「前綴和＋雙指標」的組合，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：

  • 前綴和：NTUCPC Guide〈前綴和與差分〉——先算好「前 \(i\) 個的總和」，任何一段的和就是兩個前綴和相減；吳邦一《AP325》第 1 章 P-1-6「最接近的區間和」用同一招把區間和的計算從 \(O(n^3)\) 降到 \(O(n^2)\)（教材 PDF 第 25～27 頁）。本題除了「總和」，還把奇數記 \(+1\)、偶數記 \(-1\) 做成另一組前綴和。
  • 雙指標：NTUCPC Guide〈雙指標〉——一個指標往右走的時候，另一個指標只會往同一個方向走，兩個指標合起來最多動 \(O(n)\) 次；《AP325》第 2 章 P-2-6「Two-Number problem」的第二種做法就是它（教材 PDF 第 55～56 頁，站上題目 ap325p206）。
  • vector 的 push_back／pop_back：本題替每一種「奇偶差」各開一個 vector 當桶子，尾端放進去、尾端拿出來。

簡潔題意

\(n\) 個正整數排成一列。從最左邊取走一段前綴、從最右邊取走一段後綴（兩段不能重疊；也可以只取一邊、或兩邊都不取），取出來的數裡奇數與偶數的個數要一樣多，而且總和不能超過 \(k\)。求能取到的最大總和；取不到任何東西就輸出 \(0\)（\(1 \le n \le 3 \times 10^5\)，\(1 \le k \le 10^9\)，\(1 \le a_i \le 5000\)；題目另外保證每個前綴裡「奇數個數減偶數個數」的絕對值不超過 \(2000\)）。

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

  • 子題組 1（\(20\) 分）：\(n = 1000\)。
  • 子題組 2（\(80\) 分）：無額外限制。

先拿下 20 分：枚舉前綴長度和後綴長度

「奇數與偶數一樣多」不好直接數，換個記法：奇數記 \(+1\)、偶數記 \(-1\)，一堆數的「奇偶差」就是這些 \(\pm 1\) 的總和，奇偶差是 \(0\) 就代表奇數和偶數一樣多。於是每個候選選法只要看兩個數字——總和與奇偶差——而這兩個都能用前綴和在 \(O(1)\) 算出來：

pre[i]＝前 \(i\) 個的總和，bal[i]＝前 \(i\) 個的奇偶差。前綴取前 \(i\) 個、後綴取第 \(j+1\) 個到最後（\(j \ge i\) 才不會重疊），總和就是 pre[i] + (pre[n] - pre[j])，奇偶差就是 bal[i] + (bal[n] - bal[j])。

把所有 \((i, j)\) 都試一遍（\(i = 0\) 是不取前綴、\(j = n\) 是不取後綴，都要算進去），奇偶差是 \(0\)、總和不超過 \(k\) 的裡面取最大：

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

int main() {
    int n;
    long long k;
    cin >> n >> k;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    // pre[i]：a[1..i] 的總和；bal[i]：a[1..i] 裡「奇數個數 − 偶數個數」
    vector<long long> pre(n + 1, 0);
    vector<int> bal(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + a[i];
        bal[i] = bal[i - 1] + (a[i] % 2 == 1 ? 1 : -1);
    }

    long long best = 0;                            // 什麼都不取＝0，也是合法的
    for (int i = 0; i <= n; i++)                   // 前綴取 a[1..i]
        for (int j = i; j <= n; j++) {             // 後綴取 a[j+1..n]；j >= i 才不會重疊
            long long sum = pre[i] + (pre[n] - pre[j]);
            int balance = bal[i] + (bal[n] - bal[j]);
            if (balance == 0 && sum <= k) best = max(best, sum);
        }
    cout << best << '\n';
    return 0;
}

\(n = 1000\) 時 \((i, j)\) 大約 \(5 \times 10^5\) 對，子題組 1 的 \(20\) 分穩穩到手。\(n = 3 \times 10^5\) 就是 \(4.5 \times 10^{10}\) 對，本站實測一筆要 \(36\) 秒。

從 20 分到 100 分：固定前綴，後綴只有三個條件

把前綴固定下來（總和 \(P\)、奇偶差 \(p\)），什麼樣的後綴配得上它？只有三件事：

  1. 奇偶差要是 \(-p\)：兩段加起來才是 \(0\)（圖 1）。
  2. 長度不能超過 \(n - i\)：才不會跟前綴重疊。
  3. 總和不能超過 \(k - P\)：剩下的預算。

符合這三條的後綴裡，哪一個最好？數字全是正的，所以後綴越長總和越大——要的就是最長的那一個。

圖 1：範例 1 把奇數記 +1、偶數記 −1，前綴 1 5 2 的奇偶差 +1 配後綴 8 的奇偶差 −1，加起來 0 就是奇偶一樣多，總和 16

條件 1 用桶子解決：把每個後綴長度 \(j\) 依奇偶差 sbal[j] 丟進對應的桶 bucket[sbal[j]]（長度 \(0\) 的空後綴也丟進差 \(0\) 的桶），由短到長依序放，所以每個桶裡的長度是遞增的、桶尾就是最長的。要配前綴時直接去看 bucket[-p]。

條件 2、3 都是「長度不能超過某個上限」——條件 3 也是，因為後綴總和隨長度遞增，付得起的長度自然有個上限。關鍵在於：前綴每往右長一格，這兩個上限只會變小（\(n - i\) 變小、剩下的預算變少）。所以用一個變數 allowed 記「現在最長可以用到哪個長度」，前綴每長一格就檢查 allowed 還合不合法，不合法就一直減、每減一次把那個長度從它的桶裡拿掉——而它一定是該桶的最後一個，因為桶裡的長度遞增、我們又是從最長的開始拿。這就是雙指標：\(i\) 往右走、allowed 往左走，各自最多走 \(n\) 步。

桶要開多大？前綴的奇偶差保證在 \(\pm 2000\) 內，但後綴沒有這個保證：後綴的奇偶差＝整列的奇偶差減掉前面那段前綴的奇偶差，範圍是 \(\pm 4000\)，所以加 \(4000\) 當下標、開 \(8001\) 個桶。總和最大 \(3 \times 10^5 \times 5000 = 1.5 \times 10^9\)，int 的上限 \(2147483647\) 剛好放得下，但太貼近了，用 long long 不用擔心。

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

const int OFFSET = 4000;                 // 後綴的奇偶差在 -4000 到 4000 之間，加 4000 當下標

int main() {
    int n;
    long long k;
    cin >> n >> k;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    // suf[j]：最右邊 j 個的總和；sbal[j]：最右邊 j 個的奇偶差
    vector<long long> suf(n + 1, 0);
    vector<int> sbal(n + 1, 0);
    vector<vector<int>> bucket(2 * OFFSET + 1);    // bucket[d + OFFSET]：奇偶差是 d 的後綴長度，由短到長
    bucket[OFFSET].push_back(0);                   // 長度 0 的空後綴：奇偶差 0、總和 0
    for (int j = 1; j <= n; j++) {
        suf[j] = suf[j - 1] + a[n - j + 1];
        sbal[j] = sbal[j - 1] + (a[n - j + 1] % 2 == 1 ? 1 : -1);
        bucket[sbal[j] + OFFSET].push_back(j);
    }

    long long best = 0, pre = 0;         // pre：目前前綴的總和
    int pbal = 0;                        // 目前前綴的奇偶差
    int allowed = n;                     // 後綴長度最多只能到 allowed，只會越來越小
    for (int i = 0; i <= n; i++) {       // 前綴取 a[1..i]
        if (pre > k) break;              // 前綴自己就超過預算，再長只會更糟
        // 太長（會跟前綴重疊）或太貴（超過剩下的預算）的後綴，從各自的桶尾拿掉
        while (allowed > 0 && (allowed > n - i || suf[allowed] > k - pre)) {
            bucket[sbal[allowed] + OFFSET].pop_back();
            allowed--;
        }
        vector<int> &cand = bucket[OFFSET - pbal];           // 奇偶差要是 -pbal 才抵銷得掉
        if (!cand.empty()) best = max(best, pre + suf[cand.back()]);   // 桶尾最長＝總和最大
        if (i < n) {
            pre += a[i + 1];
            pbal += (a[i + 1] % 2 == 1 ? 1 : -1);
        }
    }
    cout << best << '\n';
    return 0;
}

每個長度進桶一次、出桶最多一次，整體 \(O(n)\)；\(n = 3 \times 10^5\) 本站實測不到 \(0.1\) 秒。

另一種做法：不用雙指標，直接二分搜

看不出「上限只會變小」也沒關係：桶裡的長度是排序好的、suf 也是遞增的，兩個上限各用一次 upper_bound 找就好（對答案二分搜的工具用法見 NTUCPC Guide〈搜尋〉的「二分搜 in STL」）。先在 suf 裡找「付得起的最長長度」，和 \(n - i\) 取小的當上限，再到桶裡找不超過上限的最後一個。\(O(n \log n)\)，一樣是滿分。

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

const int OFFSET = 4000;

int main() {
    int n;
    long long k;
    cin >> n >> k;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<long long> suf(n + 1, 0);
    vector<int> sbal(n + 1, 0);
    vector<vector<int>> bucket(2 * OFFSET + 1);
    bucket[OFFSET].push_back(0);
    for (int j = 1; j <= n; j++) {
        suf[j] = suf[j - 1] + a[n - j + 1];
        sbal[j] = sbal[j - 1] + (a[n - j + 1] % 2 == 1 ? 1 : -1);
        bucket[sbal[j] + OFFSET].push_back(j);
    }

    long long best = 0, pre = 0;
    int pbal = 0;
    for (int i = 0; i <= n; i++) {
        if (pre > k) break;
        // suf 遞增：第一個「超過剩餘預算」的長度之前，都付得起
        int byBudget = upper_bound(suf.begin(), suf.end(), k - pre) - suf.begin() - 1;
        int limit = min(n - i, byBudget);                    // 不重疊、付得起，兩個上限取小的
        vector<int> &cand = bucket[OFFSET - pbal];
        int pos = upper_bound(cand.begin(), cand.end(), limit) - cand.begin() - 1;   // 桶裡 <= limit 的最後一個
        if (pos >= 0) best = max(best, pre + suf[cand[pos]]);
        if (i < n) {
            pre += a[i + 1];
            pbal += (a[i + 1] % 2 == 1 ? 1 : -1);
        }
    }
    cout << best << '\n';
    return 0;
}

測過再交：範例沒有「只取一邊」的局面

範例 1 的答案兩邊都有取、範例 2 什麼都取不到。沒蓋到的：只取一邊就是最好的、總和剛好等於 \(k\)、前後綴搶同一個數字、同一個桶裡有好幾個候選、後綴的奇偶差超過 \(\pm 2000\)、值域極端。

輸入 正確輸出 這一筆在測什麼
1 10 ／ 3 0 \(n = 1\)：一個數不可能奇偶一樣多
2 3 ／ 1 2 3 總和剛好等於 \(k\)，等號要放行
3 100 ／ 1 2 1 3 前綴 1 2 和後綴 2 1 都想要中間那個 2：重疊了只能挑一邊
4 100 ／ 1 2 7 7 3 只取前綴最好，後綴一個都不拿
4 100 ／ 7 7 2 1 3 只取後綴最好
3 7 ／ 2 4 1 5 差 \(0\) 的桶裡同時有空後綴和 4 1：要拿最長的那個
用程式造：\(2000\) 個 1 後面接 \(4000\) 個 2，\(k = 10^9\) 6000 後綴 2 … 2 的奇偶差是 \(-4000\)：桶子只開 \(\pm 2000\) 會越界
用程式造：\(n = 300000\)，4999 與 5000 交錯，\(k = 10^9\) 999999990 值域極端：總和貼近 \(10^9\)，而且要在時限內跑完

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

常犯錯誤
  • 沒檢查重疊（後綴從哪裡開始都可以）：兩個範例都剛好過，自測表第 3 列印 6；本站 \(22\) 筆測資掛 \(7\) 筆。
  • 總和要「小於」\(k\)（寫成 <）：範例過，自測表第 2 列印 0；本站掛 \(7\) 筆。
  • 桶裡拿第一個（最短的）後綴，不是最後一個：範例過，自測表第 6 列印 3；本站掛 \(6\) 筆。
  • 只取前綴（或只取後綴）：範例 1 印 10；本站掛 \(9\) 筆。
  • 以為兩段都一定要取：自測表第 4、5 列都印 0。
  • 桶只開 \(\pm 2000\)：自測表第 7 列直接當掉（下標變負數，記憶體越界）。
  • 忘了奇偶條件：範例 1 印 22、範例 2 印 19。
  • 拿 \(20\) 分的雙迴圈跑滿分測資：\(n = 3 \times 10^5\) 一筆 \(36\) 秒，本站 \(11\) 筆超時。