最佳選擇

https://zerojudge.tw/ShowProblem?problemid=o079

考點

前綴和、二分搜、資料結構

• 前綴和
• 二分搜
• 雙指針
• Mpa

思路

首先，我們觀察到的重要性質是：選擇右邊的第 $k$ 個數字後，左邊的奇數數量減去偶數數量的差值必須與右邊相反，即左右兩邊的奇偶數差相加為零。

為了快速計算任意範圍內的奇偶數差，我們可以將偶數視為 $-1$，奇數視為 $1$，並使用前綴和來維護這個差值。這樣，我們可以在 $O(1)$ 的時間內查詢任意範圍內的奇偶數差。

接著，我們從右向左枚舉每個可能的右端點，同時維護目前的奇偶數差值以及總和。為了找到符合條件的最佳左端點，我們可以使用一個 map 來記錄不同奇偶數差值出現的位置和其對應的總和。在枚舉每個右端點時，我們可以使用二分搜從合法的左端點中找到一個最佳的左端點，滿足對應的總和加上當前右端點的總和最大且不超過 $k$，並嘗試更新答案。

當然，從左做到右或從右做到左都可以。

程式碼

#include <bits/stdc++.h>
using namespace std;
// 實作量稍微大一點，所以先 define 一些好用的東西
// #define int long long
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define ff first
#define ss second

const int MAXN = 3e5 + 10;

int v[MAXN];

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // IO 優化
    unordered_map<int, vector<pii>> mp; // 用來快速查詢每個奇偶差有哪些左端點，pair 的兩個數字分別為 index 和 sum
    int n, k;
    cin >> n >> k;
    int presum = 0; // 前綴和
    int predif = 0; // 前綴奇偶差
    mp[0].push_back({0, 0}); // 處理整個陣列都被選的 edge case
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        presum += v[i]; // 前綴和加上 v[i]
        predif += v[i] % 2 ? -1 : 1; // 計算前綴奇偶差
        if (presum > k) continue;
        mp[predif].push_back({i, presum}); // 根據奇偶差把目前的端點記錄起來
    }
    int ans = mp[0].size() ? mp[0].back().ss : 0; // 處理全部都選左邊的 edge case
    int sufsum = 0; // 後綴和
    int sufdif = 0; // 後綴奇偶差
    for (int i = n; i >= 1; i--) {
        sufsum += v[i]; // 後綴和加上 v[i]
        sufdif += v[i] % 2 ? -1 : 1; // 計算後綴奇偶差
        vector<pii> endpts = mp[-sufdif]; // 所有奇偶差合法的左端點
        int l = 0;
        int r = upper_bound(all(endpts), (pii){i, -1}) - endpts.begin(); // 不考慮重疊到的
        while (l < r) { // 透過二分搜找到最佳左端點 
            int mid = (l + r) / 2;
            if (endpts[mid].ss + sufsum > k)
                r = mid;
            else
                l = mid + 1;
        }
        if (l <= 0) continue;
        ans = max(ans, endpts[l - 1].ss + sufsum); // 嘗試更新答案
    }
    cout << ans << endl; // 輸出答案
}