TIOJ 1986：郵局設置問題 ꝏ EXTREME

TIOJ 1986：郵局設置問題 ꝏ EXTREME

題目大意：數線上有 $n$ 個座標，要在其中 $k$ 個設郵局，求每個座標到自己最近之郵局座標距離和。

解法：

設越多郵局，距離和一定會變短，我們無法快速知道在設 $x$ 個郵局時的最短距離，但是可以知道有最短距離時要設幾個郵局，於是為了減少郵局設置量以滿足限制，我們其實可以在每次設置郵局時加上罰款，罰款越多，想要設置郵局的數量可能就會變少，所以可以讓罰款由大到小 $\text{or}$ 由小到大，找到滿足設置數量 $≤k$ 個時的解，因為被加上過罰款了，最後再把罰款扣掉就好了。

但是罰款金額一個一個試太累了，我們其實可以對罰款金額二分搜，找到設置數量最接近 $k$ 且小於等於 $k$ 的解，這就是著名的 $\text{aliens}$ 優化 (可參考 Wiwipedia 與 建中培訓講義)，條件是要是凸或凹函數，而這題觀察後不難發現函數是凸的。假設二分搜到最接近 $k$ 的解是 $x$，而且 $x != k$ 的話，把 總金額 $- x \times$ 罰款 會是設置 $x$ 個郵局的最佳解，並不是設置 $k$ 個郵局的。我們可以知道如果有多個最小值時，會二分搜到 $x$ 最小的，假設搜到的罰款是 $p$，在設 $x$ 個郵局的總金額最佳解是 $f(x)$，則 $f(x) + p \times x = f(k) + p \times k$，因 $f(x) + p \times x$ 是平底的，於是我們想要求的答案就是 $(f(x) + p \times x) - p \times k$，前者可以計算出來。

那要怎麼計算在罰款為 $p$ 時的解呢？可以動態規劃，如果 $i$ 是由 $pos$ 轉移過來，我們可以在 $[pos + 1, i]$ 的中位數設置郵局，那麼 $dp[i] = min (dp[pos] + dis (pos + 1, i) + p)$，$dis (l, r)$ 的計算方法就是利用前綴和，把中位數左邊到中位數的距離加上中位數右邊到中位數的距離，最後再加上罰款 $p$。

但是如果直接這樣做，跑過一遍的複雜度是 $O(n^2)$，所以我們想要更快的做法。這時候就可以用一個東西叫做四邊形優化！我們要用到的是四邊形優化裡的凸優化，假設有四個點叫做 $l, r, x, y$，我們說他們符合凸單調性就是假設從 $p_1$ 轉移到 $p_2$ 的代價是 $V (p_1, p_2)$，只要 $V (l, x) ≥ V (r, x)$，則 $V (l, y)$ 一定 $≥ V (r, y)$，相當於只要有一個時間點從 $r$ 轉移比從 $l$ 轉移好，那之後的時間點從 $r$ 轉移一定會比從 $l$ 轉移好，$r$ 就淘汰掉了 $l$。

那要怎麼把這個性質套在這題呢？可以觀察到如果在某個 $x$ 點的 $dp$ 值從 $r$ 轉移時比從 $l$ 轉移時好，那麼在 $x$ 之後的所有 $y$ 點從 $r$ 轉移都會比從 $l$ 轉移好。該怎麼證明呢？

我們知道 $V (l, x) ≥ V (r, x)$，
$→ dp[l] + dis (l + 1, x) + \text{penalty} ≥ dp[r] + dis (r + 1, x) + \text{penalty}$
$→ dis (l + 1, x) - dis (r + 1, x) ≥ dp[r] - dp[l]$

不等式右半部不會變，看左半部，假設現在換成 $y$ 轉移了，那左半部會變成 $dis (l + 1, y) - dis (r + 1, y)$，如果要繼續滿足不等式，$dis (l + 1, y)$ 比 $dis (l + 1, x)$ 多出來的一定要大於等於 $dis (r + 1, y)$ 比 $dis (r + 1, y)$ 多出來的，以下的有點不嚴謹：假設從 $x$ 跑到 $x + 1$，那從 $l$ 轉移過來多的距離就是 $a[x + 1] - a[mid]$ ($mid$ 為 $[(l + 1) + (x + 1)] / 2$)，從 $r$ 轉移過來多的距離就是 $a[x + 1] - a[mid]$ ($mid$ 為 $[(r + 1) + (x + 1)] / 2$)，因為 $a[l + 1]$ 到 $a[x + 1]$ 的距離比 $a[r + 1]$ 到 $a[x + 1]$ 的距離長 (因為 $l$ 在 $r$ 左邊)，所以 $dis (l + 1, x + 1) - dis (r + 1, x + 1) ≥ dp[r] - dp[l]$，然後我們把 $x$ 替換成 $x + 1$，就可以推到所有 $y$ 的情況。只是在移 $x$ 的時候 $mid$ 有可能會改變，但是他最後還是會符合結果的，只是我不會證，就用上面直觀的看法就好了。

四邊形凸性優化實作的方法就是在 $\text{deque}$ 裡存一個 $\text{tuple}$，紀錄 $(pos, l, r)$，代表目前從 $pos$ 轉移到區間 $[l, r]$ 是最佳的。一開始先把 $r$ 在目前 $i$ 左邊的 $\text{tuple pop}$ 掉，把 $dp[i]$ 從 $\text{deque}$ 最前端的 $pos$ 轉移過來，之後看看從 $i$ 轉移到之後的點會不會比 $\text{deque}$ 最後端的 $pos$ 轉移好，如果比較好，就可以 $\text{pop}$ 掉。如果當前的 $\text{tuple}$ 都 $\text{pop}$ 光了，就 $\text{push}$ 一個 $(i, i + 1, n)$；如果從 $i$ 轉移到 $\text{deque}$ 最後端的 $r$ 不會比較好，就 $\text{push}  (i, r + 1, n)$；否則就要搜尋 $i$ 要從哪裡開始轉移會比較好，因為有凸單調性，所以可以二分搜尋位置，之後就可以 $\text{push}$ 了。

時間複雜度 $O (n \times log(C) \times log(n))$，$log(C)$ 是在做 $\text{aliens}$ 時二分搜 $\text{penalty}$，$log(n)$ 是在四邊形優化的二分搜開始轉移點。$C$ 我試出來設成 $5e10$ 可以過。此題跟 TIOJ 1449 的差異就是那一題用 $O (n^2)$ 就可以過了，但是因為這一題用了 $\text{aliens}$，所以就可以壓到 $O (n \times log(C) \times log(n))$，只能說 $\text{aliens}$ 真的非常神奇，這一題也是我第一次寫到凸性優化和第二次寫到 $\text{aliens}$，也讓我更深入了解到這兩種算法。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 3e5 + 5;

struct Seg {int pos, l, r;};

int n, k, penalty;
int a[SIZE], pre[SIZE];
pair<int, int> dp[SIZE];
deque<Seg> st;

int dis (int l, int r) {
    int mid = (l + r) / 2, ldis, rdis;
    ldis = (mid - l + 1) * a[mid] - (pre[mid] - pre[l - 1]);
    rdis = (pre[r] - pre[mid - 1]) - (r - mid + 1) * a[mid];
    return ldis + rdis;
}

pair<int, int> cal (int l, int r) {
    return {dp[l].F + dis (l + 1, r) + penalty, dp[l].S + 1};
}

bool ok (int p) {
    penalty = p;
    st.clear();
    st.push_back ({0, 1, n});
    FOR (i, 1, n) {
        while (st.size() && st[0].r < i) {
            st.pop_front();
        }
        dp[i] = cal (st[0].pos, i);
        while (st.size() && cal (i, st.back().l) <= cal (st.back().pos, st.back().l)) {
            st.pop_back();
        }
        if (!st.size()) {
            st.push_back ({i, i + 1, n});
        } else if (cal (i, st.back().r) >= cal (st.back().pos, st.back().r)) {
            if (st.back().r != n) {
                st.push_back ({i, st.back().r + 1, n});
            }
        } else {
            auto [pos, l, r] = st.back();
            while (l < r) {
                int mid = (l + r) / 2;
                if (cal (i, mid) > cal (pos, mid)) {
                    l = mid + 1;
                } else {
                    r = mid;
                }
            }
            st[st.size() - 1].r = l - 1;
            st.push_back ({i, l, n});
        }
    }
    return dp[n].S <= k;
}

void solve() {
    cin >> n >> k;
    FOR (i, 1, n) cin >> a[i];
    sort (a + 1, a + n + 1);
    FOR (i, 1, n) pre[i] = pre[i - 1] + a[i];
    int l = 0, r = 5e10;
    while (l < r) {
        int mid = (l + r) / 2;
        if (ok (mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    ok (l);
    cout << dp[n].F - k * penalty << '\n';
}

int32_t main() {
    Waimai;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！