https://zerojudge.tw/ShowProblem?problemid=o079
考點#
前綴和、二分搜、資料結構
- 前綴和
- 二分搜
- 雙指針
- Map
思路#
首先，我們觀察到的重要性質是：選擇右邊的第 \(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; // 輸出答案
}
