Codeforces Round #251 Div2 D：二分答案最小化調整代價

Codeforces Round #251 Div2 D：二分答案最小化調整代價

給定數組 a（長 n）和 b（長 m），可對元素進行 ±1 操作（代價 1）。求最小總代價使 min(a) ≥ max(b)。

關鍵觀察

存在閾值 x，使調整後 a_i ≥ x 且 b_j ≤ x。
代價函數 f(x) = Σ max(0, x-a_i) + Σ max(0, b_j-x) 是凸函數。
最優 x 必在 a ∪ b 的元素中（或其相鄰整數）。

算法流程

1. 收集所有 a_i, b_j 到向量 vals，排序去重。
2. 預處理 a 前綴和 sa，b 後綴和 sb。
3. 對每個候選 x ∈ vals，二分/雙指針計算 f(x)，取最小值。

代價計算

ll cost(ll x) {
    // a 中 < x 的元素需增加到 x
    int pa = lower_bound(a+1, a+n+1, x) - a - 1;
    ll c1 = (ll)pa * x - sa[pa];
    // b 中 > x 的元素需減少到 x
    int pb = upper_bound(b+1, b+m+1, x) - b;
    ll c2 = sb[pb] - (ll)(m - pb + 1) * x;
    return c1 + c2;
}

完整邏輯

sort(a+1, a+n+1); sort(b+1, b+m+1);
for (int i=1; i<=n; i++) sa[i] = sa[i-1] + a[i];
for (int i=m; i>=1; i--) sb[i] = sb[i+1] + b[i];
vector cand;
for (int i=1; i<=n; i++) cand.push_back(a[i]);
for (int i=1; i<=m; i++) cand.push_back(b[i]);
sort(cand.begin(), cand.end());
cand.erase(unique(cand.begin(), cand.end()), cand.end());
ll ans = INF;
for (ll x : cand) ans = min(ans, cost(x));
printf("%lld\n", ans);

複雜度

• 排序 O((n+m) log(n+m))。
• 候選值 ≤ n+m，每個 O(log n + log m) 計算代價。
• 總體 O((n+m) log(n+m))，滿足 1e5 規模。

核心技巧

• 凸函數最優解在離散點：只需檢查數組元素值。
• 前綴/後綴和 將區間求和降為 O(1)。
• 二分查找定位分界：lower_bound/upper_bound 區分 和 >x。