# APCS實作題2024年6月第4題：最佳選擇

> 日期：2024年8月19日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=o079)

## 題目

### 問題描述

給一個長度為 $n$ 的正整數序列 $a_1, a_2, \dots, a_n$，你可以執行多次操作 (包含0次)，每次操作只能選擇這個序列的第一個或最後一個數字，再將這個數字從序列中刪除並自己搜集起來。

求滿足總和不超過 $k$ 且搜集的數字奇數和偶數個數相同的條件下，所能搜集的數字總和最大為多少。
<br />

### 輸入說明

第一行輸入兩個正整數 $n, k~(1 \leq n \leq 3 \times 10^5, 1 \leq k \leq 10^9)$。

第二行有 $n$ 個正整數 $a_1, a_2, \dots, a_n ~(1 \leq a_i \leq 5 \times 10^3)$。

保證 $\forall i \in [1, n]$，前 $i$ 個數字的奇數和偶數數量差距不超過 $2 \times 10^3$。

子題配分
- 20分：$n = 10^3$
- 80分：無限制

<br />

### 輸出格式

輸出滿足題目需求的最大值。
<br />

### 範例輸入1

8 22
1 5 2 2 9 3 5 8

### 範例輸出1

16

### 範例輸入2

7 20
7 7 8 2 8 9 5

### 範例輸出2

0

<br /><br />

## Python 程式碼

### 寫法1

費時最久約為 1.1 s，使用記憶體最多約為 49.4 MB，通過測試。

from collections import defaultdict

n, k = map(int, input().split())  # 讀取數量 n，總和上限 k
a = list(map(int, input().split()))  # 讀取資料 a
""" 處理前綴 """
psum = 0  # 前綴和
pdif = defaultdict(list)  # 前綴部分，奇數數量 - 偶數數量對應的前綴和，如果 key 值不存在對應到空串列
dif = 0  # 從左到右，奇數數量 - 偶數數量
for i in range(n):  # 從左到右掃過 a
    psum += a[i]  # 前綴和第 i 位的前綴和
    dif += 1 if a[i]&1 else -1  # 若 a[i] 為奇數 dif 加 1，反之減 1
    pdif[dif].append(psum)  # 將 psum 加入對應的 key 值資料
""" 處理特例 """
if k > psum: k = psum  # 如果 k 大於全部的總和，將 k 更新為 psum
while pdif[0] and pdif[0][-1] > k: pdif[0].pop()  # 全部資料皆由左向右選，由最後一位開始，如果超出上限則移除此資料
ans = pdif[0][-1] if pdif[0] else 0  # 答案預設為全部資料皆由左向右選取的最大值或 0
""" 處理後綴 """
ssum = 0  # 後綴和
sdif = 0  # 從右到左，偶數數量 - 奇數數量
for i in range(n-1, 0, -1):  # 依序檢查 a[n-1] ~ a[1]
    ssum += a[i]  # 後綴和
    sdif += 1 if a[i]&1 == 0 else -1  # 若 a[i] 為偶數 dif 加 1，反之減 1
    if abs(sdif) > 2000: continue  # 偶數數量 - 奇數數量大於 2000，超出題目範圍，找下一位
    cand = pdif[sdif]  # 由左到右可能的前綴和
    if not cand: continue # 如果沒有對應的前綴和，找下一位
    while cand and ssum + cand[-1] > k: cand.pop()  # 從 cand 最後一位開始向左找，總和只會越來越小，結束時可能是空串列或符合條件的最大值
    if cand: ans = max(ans, ssum + cand[-1])  # 更新答案
""" 結束 for 迴圈 """
print(ans)  # 印出答案

<br />

如果在第11、12行之間加入

if psum > k: continue

刪除第15行

while pdif[0] and pdif[0][-1] > k: pdif[0].pop()

可以少存一些資料，費時最久約為 1.1 s，使用記憶體最多約為 49.1 MB，通過測試。

from collections import defaultdict

n, k = map(int, input().split())  # 讀取數量 n，總和上限 k
a = list(map(int, input().split()))  # 讀取資料 a
""" 處理前綴 """
psum = 0  # 前綴和
pdif = defaultdict(list)  # 前綴部分，奇數數量 - 偶數數量對應的前綴和，如果 key 值不存在對應到空串列
dif = 0  # 從左到右，奇數數量 - 偶數數量
for i in range(n):  # 從左到右掃過 a
    psum += a[i]  # 前綴和第 i 位的前綴和
    dif += 1 if a[i]&1 else -1  # 若 a[i] 為奇數 dif 加 1，反之減 1
    if psum > k: continue  # psum 超出上限，找下一位
    pdif[dif].append(psum)  # 將 psum 加入對應的 key 值資料
""" 處理特例 """
if k > psum: k = psum  # 如果 k 大於全部的總和，將 k 更新為 psum
ans = pdif[0][-1] if pdif[0] else 0  # 答案預設為全部資料皆由左向右選取的最大值或 0
""" 處理後綴 """
ssum = 0  # 後綴和
sdif = 0  # 從右到左，偶數數量 - 奇數數量
for i in range(n-1, 0, -1):  # 依序檢查由右到左取 a[n-1] ~ a[1]
    ssum += a[i]  # 後綴和
    sdif += 1 if a[i]&1 == 0 else -1  # 若 a[i] 為偶數 dif 加 1，反之減 1
    if abs(sdif) > 2000: continue  # 偶數數量 - 奇數數量大於 2000，超出題目範圍，找下一位
    cand = pdif[sdif]  # 由左到右可能的前綴和
    if not cand: continue # 如果沒有對應的前綴和，找下一位
    while cand and ssum + cand[-1] > k: cand.pop()  # 從 cand 最後一位開始向左找，總和只會越來越小，結束時可能是空串列或符合條件的最大值
    if cand: ans = max(ans, ssum + cand[-1])  # 更新答案
""" 結束 for 迴圈 """
print(ans)  # 印出答案

<br /><br />

### 寫法2，用二分搜尋法從 cand 中找符合條件的最大值

沒想到比寫法1還慢，費時最久約為 2.4 s，使用記憶體最多約為 49.1 MB，通過測試。

from collections import defaultdict
from bisect import bisect_right

n, k = map(int, input().split())  # 讀取數量 n，總和上限 k
a = list(map(int, input().split()))  # 讀取資料 a
""" 處理前綴 """
psum = 0  # 前綴和
pdif = defaultdict(list)  # 前綴部分，奇數數量 - 偶數數量對應的前綴和，如果 key 值不存在對應到空串列
dif = 0  # 從左到右，奇數數量 - 偶數數量
for i in range(n):  # 從左到右掃過 a
    psum += a[i]  # 前綴和第 i 位的前綴和
    dif += 1 if a[i]&1 else -1  # 若 a[i] 為奇數 dif 加 1，反之減 1
    if psum > k: continue  # psum 超出上限，找下一位
    pdif[dif].append(psum)  # 將 psum 加入對應的 key 值資料
""" 處理特例 """
if k > psum: k = psum  # 如果 k 大於全部的總和，將 k 更新為 psum
ans = pdif[0][-1] if pdif[0] else 0  # 答案預設為全部資料皆由左向右選取的最大值或 0
""" 處理後綴 """
ssum = 0  # 後綴和
sdif = 0  # 從右到左，偶數數量 - 奇數數量
for i in range(n-1, 0, -1):  # 依序檢查由右到左取 a[n-1] ~ a[1]
    ssum += a[i]  # 後綴和
    sdif += 1 if a[i]&1 == 0 else -1  # 若 a[i] 為偶數 dif 加 1，反之減 1
    if abs(sdif) > 2000: continue  # 偶數數量 - 奇數數量大於 2000，超出題目範圍，找下一位
    cand = pdif[sdif]  # 由左到右可能的前綴和
    if not cand: continue # 如果沒有對應的前綴和，找下一位
    low, high = 0, bisect_right(cand, k-ssum)
    while high > low:
        mid = (high - low) // 2 + low
        if ssum + cand[mid] > k: high = mid
        else: low = mid + 1# 從 cand 最後一位開始向左找，總和只會越來越小，結束時可能是空串列或符合條件的最大值
    if low <= 0: continue
    ans = max(ans, ssum + cand[low-1])  # 更新答案
""" 結束 for 迴圈 """
print(ans)  # 印出答案

<br /><br />

## C++ 程式碼

### 寫法1，與上方的 Python 程式碼原理相同，用 unordered_map 儲存奇、偶數差對應的前綴和

第17筆測資超時。

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);  // 加速
    int n, k; cin >> n >> k;  // 讀取數量 n，總和上限 k
    vector<int> a (n, 0);  // 儲存資料用的陣列 a
    /* 處理前綴 */
    unordered_map<int, vector<int>> pdif;  // 前綴部分，奇數數量 - 偶數數量對應的前綴和
    int dif = 0, psum = 0;  // dif 從左到右，奇數數量 - 偶數數量；psum 前綴和
    for(int i=0; i<n; i++) {  // 執行 n 次
        cin >> a[i];  // 讀取資料 a
        psum += a[i];  // 第 i 位的前綴和
        dif += a[i]&1 ? 1 : -1;  // 若 a[i] 為奇數加 1，反之減 1
        if (psum > k) continue;  // psum 超出上限，找下一位
        pdif[dif].push_back(psum);  // 將 psum 加入對應的 key 值資料
    }
    /* 處理特例 */
    if (k > psum) k = psum;  //  如果 k 大於全部的總和，將 k 更新為 psum
    int ans = !pdif[0].empty() ? pdif[0].back() : 0;  // 答案預設為全部資料皆由左向右選取的最大值或 0
    /* 處理後綴 */
    int ssum = 0, sdif = 0;  // 後綴和，從右到左偶數數量 - 奇數數量
    for(int i=n-1; i>0; i--) {  //  依序檢查 a[n-1] ~ a[1]
        ssum += a[i];  // 後綴和
        sdif += a[i]&1 ? -1 : 1;  // a[i] 為奇數減 1，反之加 1
        if (abs(sdif) > 2000) continue;  // 偶數數量 - 奇數數量大於 2000，超出題目範圍，找下一位
        vector<int> cand = pdif[sdif];  //  由左到右可能的前綴和
        if (cand.empty()) continue;  // 如果沒有對應的前綴和，找下一位
        while(!cand.empty() && ssum + cand.back() > k) cand.pop_back();  // 從 cand 最後一位開始向左找，總和只會越來越小，結束時可能是空陣列或符合條件的最大值
        if (!cand.empty()) ans = max(ans, ssum + cand.back());  // 更新答案
    }
    /* 結束 for 迴圈 */
    cout << ans << "\n";  // 印出答案
    return 0;
}

<br /><br />

### 寫法2，與寫法1原理相同，改用二維陣列儲存奇、偶數差對應的前綴和

還是會在第17筆測資超時。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);  // 加速
    int n, k; cin >> n >> k;  // 讀取數量 n，總和上限 k
    vector<int> a (n, 0);  // 儲存資料用的陣列 a
    /* 處理前綴 */
    int m = 2000;  // 奇數數量 - 偶數數量最多差 2000
    // 前綴部分，奇數數量 - 偶數數量對應的前綴和，奇數數量、偶數數量相等的資料位於索引值 2000，奇數多放前面，偶數多放後面
    vector<vector<int>> pdif (m+m+1, vector<int> ());
    pdif[m].push_back(0);  // 於奇數數量、偶數數量相等處先放入 0
    int dif = 0, psum = 0;  // dif 從左到右，奇數數量 - 偶數數量；psum 前綴和
    for(int i=0; i<n; i++) {  // 執行 n 次
        cin >> a[i];  // 讀取資料 a
        psum += a[i];  // 第 i 位的前綴和
        dif += a[i]&1 ? 1 : -1;  // 若 a[i] 為奇數加 1，反之減 1
        if (psum > k) continue;  // psum 超出上限，找下一位
        pdif[m-dif].push_back(psum);  // 將 psum 加入對應的索引值
    }
    /* 處理特例 */
    if (k > psum) k = psum;  //  如果 k 大於全部的總和，將 k 更新為 psum
    int ans = !pdif[m].empty() ? pdif[m].back() : 0;  // 答案預設為全部資料皆由左向右選取的最大值或 0
    /* 處理後綴 */
    int ssum = 0, sdif = 0;  // 後綴和，從右到左偶數數量 - 奇數數量
    for(int i=n-1; i>0; i--) {  //  依序檢查 a[n-1] ~ a[1]
        ssum += a[i];  // 後綴和
        sdif += a[i]&1 ? -1 : 1;  // a[i] 為奇數減 1，反之加 1
        if (abs(sdif) > 2000) continue;  // 偶數數量 - 奇數數量大於 2000，超出題目範圍，找下一位
        vector<int> cand = pdif[m-sdif];  //  由左到右可能的前綴和
        if (cand.empty()) continue;  // 如果沒有對應的前綴和，找下一位
        while(!cand.empty() && ssum + cand.back() > k) cand.pop_back();  // 從 cand 最後一位開始向左找，總和只會越來越小，結束時可能是空陣列或符合條件的最大值
        if (!cand.empty()) ans = max(ans, ssum + cand.back());  // 更新答案
    }
    /* 結束 for 迴圈 */
    cout << ans << "\n";  // 印出答案
    return 0;
}

<br /><br />

### 寫法3，用二分搜尋法從 cand 中找符合條件的最大值

費時最久約為 0.3 s，使用記憶體最多約為 3.6 MB，通過測試。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);  // 加速
    int n, k; cin >> n >> k;  // 讀取數量 n，總和上限 k
    vector<int> a (n, 0);  // 儲存資料用的陣列 a
    /* 處理前綴 */
    int m = 2000;  // 奇數數量 - 偶數數量最多差 2000
    // 前綴部分，奇數數量 - 偶數數量對應的前綴和，奇數數量、偶數數量相等的資料位於索引值 2000，奇數多放前面，偶數多放後面
    vector<vector<int>> pdif (m+m+1, vector<int> ());
    pdif[m].push_back(0);  // 於奇數數量、偶數數量相等處先放入 0
    int dif = 0, psum = 0;  // dif 從左到右，奇數數量 - 偶數數量；psum 前綴和
    for(int i=0; i<n; i++) {  // 執行 n 次
        cin >> a[i];  // 讀取資料 a
        psum += a[i];  // 第 i 位的前綴和
        dif += a[i]&1 ? 1 : -1;  // 若 a[i] 為奇數加 1，反之減 1
        if (psum > k) continue;  // 如果 psum 大於 k，超過上限，找下一個
        pdif[m-dif].push_back(psum);  // 將 psum 加入對應的索引值
    }
    /* 處理特例 */
    if (k > psum) k = psum;  //  如果 k 大於全部的總和，將 k 更新為 psum
    //while(!pdif[m].empty() && pdif[m].back() > k) pdif[m].pop_back();  // 全部資料皆由左向右選，由最後一位開始，如果超出上限則移除此資料
    int ans = !pdif[m].empty() ? pdif[m].back() : 0;  // 答案預設為全部資料皆由左向右選取的最大值或 0
    /* 處理後綴 */
    int ssum = 0, sdif = 0;  // 後綴和，從右到左偶數數量 - 奇數數量
    for(int i=n-1; i>0; i--) {  //  依序檢查 a[n-1] ~ a[1]
        ssum += a[i];  // 後綴和
        sdif += a[i]&1 ? -1 : 1;  // a[i] 為奇數減 1，反之加 1
        if (abs(sdif) > 2000) continue;  // 偶數數量 - 奇數數量大於 2000，超出題目範圍，找下一位
        vector<int> cand = pdif[m-sdif];  //  由左到右可能的前綴和
        if (cand.empty()) continue;  // 如果沒有對應的前綴和，找下一位
        int low = 0, high = upper_bound(cand.begin(), cand.end(), k-ssum) - cand.begin();  // 從 cand 找目標值 k-ssum 的索引值下限 low、上限 high
        while(high > low) {  // 二分搜尋法
            int mid = (high - low)/2 + low;  // 中間值
            int tmp = ssum + cand[mid];  // 總和
            if (tmp > k) high = mid;  // 如果 tmp 大於 k，向左找，降低 high
            else low = mid + 1;  // 反之，向右找，提升 low
        }
        if (low <= 0) continue;  // 沒有找到目標值
        if (ssum + cand[low-1] <= k) ans = max(ans, ssum + cand[low-1]);  // 更新答案
    }
    /* 結束 for 迴圈 */
    cout << ans << "\n";  // 印出答案
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`