資結貪心

反悔貪心¶

通常是利用某個條件達到一定的值時，我們再進去貪心，例如排程的時間總和已經大於我們限制的時間，或是當先前所做的決策比目前的決策更劣，我們就會將進行反悔。

貪心與動態規劃的使用時機

貪心與動態規劃相同點是要求原問題必須有最優子結構。而不同點在於貪心法的計算方式為 Top down，並不等待子問題求解完畢後再選擇使用哪一個，而是通過一種策略直接選擇一個子問題去求解，沒被選擇的子問題直接拋棄。這種所謂「最優選擇」的正確性需要用歸納法證明。而動態規劃不管是採用自 top down 或 bottom up 的計算方式，都是從邊界開始向上得到目標問題的解（即考慮所有子問題）。

至於怎樣判斷是貪心還是 dp? 就看能否判斷貪心是否會壞掉，如果能證明貪心不可行，可能就是 dp 求解了。

通常在 n 比較大的題目時，dp 能做的轉移式會花的時間比較高，這時就可以考慮貪心，一般貪心都能在 O(n) 或 O(n log n) 的時間求解，而 dp 則是要看狀態與轉移的時間。

反悔自動機¶

即設計一種反悔策略，使得隨便一種貪心策略都可以得到正解。基本的設計思路是：每次選擇直觀上最接近全局最優解的貪心策略，若發現最優解不對，就想辦法自動支持反悔策略。（這就是自動機的意思）

具體題目具體分析。一般需要反悔自動機的題都是通過差值巧妙達到反悔的目的。

CF865D Buy Low Sell High

已知接下來 $n$ 天的股票價格，每天你可以做其中一件事

買進一股股票
賣出一股股票
什麼也不做

$n$ 天之後你手上不能有多餘的股票，求利潤最大多少

$2 \leq n \leq 3 \times 10^{5}$

思路

我們將每天的價格視為一個個"選項"，壓入小根堆中，為了確保買入操作在賣出操作之前，我們從前往後掃描 p，對於現在的價格 p[i]，如果堆頂元素 p[j] 滿足 p[j] < p[i]，那麼，我們取出堆頂，在第 j 天買入股票，在第 i 天賣出股票，此時，我們就可以獲得 p[i] - p[j] 的收益。

然而，如果之後有 p[k] 滿足 p[k] > p[i]，那麼，我們目前所做的決策可能不是最優的，如何反悔？

於是，當我們進行上述操作時，我們將 p[i] 也壓入堆中，增加一個 p[i] 的選項，彈出時，我們相當於將 p[j] 按照 p[i] 的價格又買了回來

這個跟期權的概念相關

code

void solve() {
    priority_queue<int, vector<int>, greater<int>> pq;
    cin >> n;

    for (int i = 1; i <= n; ++i) {
        cin >> x;

        pq.push(x);
        if (pq.size() && pq.top() < x) {
            ans += x - pq.top(); 
            pq.pop();
            pq.push(x);
        }
    }
    cout << ans << "\n";
}

洛谷 P1792 [国家集训队]种树

給定長度為 $n$ 的環形陣列，第 $i$ 個位置有權值 $a_{i}$ ，求相鄰的不能同時選的情況下選 $m$ 個位置的權值總和最大能多少

$n, m \leq 2 \times 10^{5}$

思路

考慮這個問題的簡化版本：我們去掉「不能選相鄰的土地」的條件，那麼問題就變成了一個非常顯而易見的貪心：排序，選最大的 $m$ 個

只是我們必須要能支援反悔動作，我們選定 $a [i]$ 之後，有什麼情況是跟這個情況互相對立的嗎 ? 答案就是 $a [i - 1] + a [i + 1]$ ，因為當前既然選了 $a [i]$ 代表他是當前最大的，那如果只選擇 $a [i - 1]$ 或只選擇 $a [i + 1]$ 顯然直接選 $a [i]$ 還會更好

所以我們貪心的策略就是支援選了 $a [i]$ 之後，將 $a [i - 1]$ 和 $a [i + 1]$ 從環上刪掉，將 $a [i]$ 改成 $(a [i - 1] + a [i + 1]) - a [i]$

code

priority_queue<pii> pq;
void init() {
    cin >> n >> m;
    if (m * 2 > n) {
        cout << "Error\n";
        exit(0);
    }
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        next[i] = i + 1;
        pre[i] = i - 1;
        pq.push(make_pair(a[i], i));
    }
    pre[1] = n;
    next[n] = 1;
}

void del(int x) {
    next[pre[x]] = next[x];
    pre[next[x]] = pre[x];
    deleted[x] = true;
}

void greed() {
    while (deleted[pq.top().id]) pq.pop();
    int x = pq.top().id;
    pq.pop();
    ans += a[x];
    a[x] = a[pre[x]] + a[next[x]] - a[x];
    del(pre[x]);
    del(next[x]);
    pq.push(make_pair(a[x], x));
}

void work() {
    for (int i = 1; i <= m; i++) greed();
    cout << ans << "\n";
}

USACO 2012 FEB Cow Coupons

有 $n$ 頭牛，目前有 $m$ 元，還有 $k$ 張優惠券。第 $i$ 頭牛的價格為 $p_{i}$ ，如果使用優惠券則為 $c_{i}$ 。問最多能買到多少頭牛

$k \leq n \leq 5 \times 10^{4}, c_{i} \leq p_{i} \leq 10^{9}, 1 \leq m \leq 10^{14}$

思路

一個直覺的想法就是維護最小堆，將每個物品的 p[i], c[i] 都加入裡面，每次 pop 最小的出來，若沒取過就直接取。但這樣若優惠券都被用完了，後面的 i 就只能以 p[i] 來取，但說不定將一個優惠券移過來用在 i 上總花費比用 p[i] 買來的更便宜，所以我們需要一個反悔的操作，維護的是 (p[j] - c[j])，若對於 i 來說 c[i] + (p[j] - c[j]) < p[i]，代表可將優惠券移過來用在 i 上。

實作上來說，我們可以開三個 min heap，一個存每一頭牛的原價 P，一個存每一頭奶牛使用優惠卷後的價格 C，一個存放原價和使用優惠卷後的價格的差 delta。一開始先把所有的 c[i] 放入 C，p[i] 放入 P，然後在存放差值的隊列中放入 k 個 0，表示目前有 k 張優惠卷可以使用，即不用補差價。

接著便是調整優惠卷的使用。在剩下的錢還沒用完的情況下，我們每一次取出存放 C 和 P 的 top，根據貪心，如果 P.top() < C.top() + delta.top()，就用原價 p[i] 買入，否則，我們就使用優惠卷，進行反悔貪心。最後，我們把這頭乳牛打上標記，防止之後再被取出。

註 : 有些博客只有維護未購買的牛的 $p_{i}$ 的 min heap，這是錯誤的，要同時維護 $c_{i}$ 和 $p_{i}$ 才有最優解，因為「對於剩下的無非兩種選擇， $p$ 買， $c$ 買」兩種都要同時考慮

code

#include <bits/stdc++.h>
#define int long long

using namespace std;
using pii = pair<int, int>;

const int MAXN = 50010;

int n, k, m;
int p[MAXN], c[MAXN];
bool buy[MAXN];  // buy[i] 表示第 i 個物品是否被買過
int ans = 0;
priority_queue<pii, vector<pii>, greater<pii>> P, C;
priority_queue<int, vector<int>, greater<int>> delta;

signed main() {
    cin >> n >> k >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> p[i] >> c[i];
        P.push(make_pair(p[i], i));
        C.push(make_pair(c[i], i));
    }
    for (int i = 1; i <= k; ++i) {
        delta.push(0);
    }
    while (!P.empty()) {
        auto [pval, pid] = P.top();
        auto [cval, cid] = C.top();
        if (buy[pid]) {  // 如果被買過了，就跳過
            P.pop();
            continue;
        }
        if (buy[cid]) {
            C.pop();
            continue;
        }
        if (delta.top() + cval > pval) {  // 用原價買 i 比較划算
            m -= pval;
            P.pop();
            buy[pid] = true;
        } else {  // 否則的話，就是用優惠券買 i 比較划算
            m -= cval + delta.top();
            delta.pop();
            C.pop();
            buy[cid] = true;
            delta.push(p[cid] - c[cid]);
        }
        if (m >= 0) {
            ans++;
        } else {
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

反悔堆¶

即通過堆（大根堆、小根堆）來維護當前貪心策略的最優解，若發現最優解不對，就退回上一步，更新最優解。

由於堆的性質，使得堆的首數據一定是最優的，這就可以實現快速更新最優解。

區間調度問題 - 最大總權重 [USACO09OPEN] Work Scheduling G

有 $n$ 項工作，每項工作有一個截止時間 $t_{i}$ ，完成每項工作可以得到利潤 $w_{i}$ ，求最大可以得到多少利潤。

code

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].time >> a[i].w;
    sort(a + 1, a + 1 + n);

    for (int i = 1; i <= n; i++) {
        if (a[i].time <= pq.size()) {
            if (a[i].w > pq.top()) {
                ans += a[i].w - pq.top();
                pq.pop();
                pq.push(a[i].w);
            }
        } else {
            ans += a[i].w;
            pq.push(a[i].w);
        }
    }

    cout << ans << "\n";
}

full code : http://codepad.org/pMPsRor9

洛谷 P4053 [JSOI2007] 建筑抢修

參見此處

CF 1271D Portals

你需要依照 $1, 2, . . ., n$ 的順序依次征服城堡。你一開始有 $k$ 個士兵，第 $i$ 個城堡有 $a_{i}$ 代表征服它所需的最少士兵數量，征服城堡後可以獲得 $b_{i}$ 個士兵，城堡有一個權重 $c_{i}$

如果你在城堡中留下至少一名士兵進行防守，該城堡就會被視為防守成功。征服城堡後可以留下士兵進行防守，也可以使用城堡之間的傳送門，傳送一個士兵過去。如果你沒有足夠的士兵來征服下一個城堡，則遊戲失敗

你的目標是在征服所有城堡的前提下最大化所有防守成功城堡的權重之和

思路

一路掃過去，每次都假定留守所有可留守的點，發現當前的士兵不夠則從已留守的點中選取權重最小的放棄留守對於每個 $u_{i} \to v$ 我們只留編號最大的 $max (u_{i}) \to v$ 這條邊，因為越後面你的軍隊會越大，也越容易成功留守

基於以上的策略，預處理出每個點可留守的集合，遍歷到該點直接將可留守的全部 push 到已留守集合中，再遍歷下一個點。在遍歷點過程中發現士兵不夠，pop 已留守集合，如果 pop 空了還不夠，說明遊戲失敗。

詳細見代碼

code

void init() {
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i] >> c[i];
        last[i] = i;
    }
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        last[v] = max(last[v], u);
    }
    for (int i = 1; i <= n; i++) {
        add_edge(last[i], i);
        // edge (last[i] -> i)
    }
}
void solve() {
    priority_queue<int, vector<int>, greater<int>> pq;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        while (k < a[i] && !pq.empty()) k++, pq.pop();
        if (k < a[i]) {
            cout << "-1\n";
            return;
        }
        k += b[i];
        for (auto v : G[u]) {
            pq.push(c[v]);
            k--;
        }
    }
    while (k < 0 && !pq.empty()) pq.pop();
    if (k < 0) {
        cout << "-1\n";
        return;
    }
    while (!pq.empty()) ans += pq.top(), pq.pop();
    cout << ans << "\n";
}

題目¶

2023 成大初賽 pC. 大富翁

給 $a_{1} \sim a_{n}$ ， $a_{i}$ 表示第 $i$ 天的收入，給 $b_{1} \sim b_{n}$ ， $b_{i}$ 表示第 $i$ 天的花費上限，另外每天花完錢後餘額不能是負數。給指定的 $k$ 天，這 $k$ 天結束的時候，身上剩下的錢要剛好是 0 元。目標是有花錢的天數要愈少愈好。

$1 \leq k \leq n \leq 10^{6}, 1 \leq a_{i}, b_{i} \leq 10^{9}$

思路

$a_{n}$ 的收入，只能在 $b_{n}$ 花掉
$a_{n - 1}$ 的收入，只能是 $b_{n - 1}$ or $b_{n}$ 花掉
$a_{n - 2}$ 的收入，只能是 $b_{n - 2}$ or $b_{n - 1}$ or $b_{n}$ 花掉
觀察最後一天，如果 $a_{n} > 0$ ，那 $b_{n}$ 就一定要使用
$b_{n}$ 一定要使用的前提下， $b_{n} - a_{n}$ 是多來還能花費的，這個時候會優先花 $a_{n - 1}$ 的收入
如果還有剩，再拿去花 $a_{n - 2}, a_{n - 3}, a_{n - 4}, . .$ 的收入
從後往前維護大的 $b_{i}$

code

int solve(vector<int> a, vector<int> b) {
    int n = a.size();
    priority_queue<int> pq;
    int rest = 0;
    for (int i = n - 1; i >= 0; i--) {
        pq.push(b[i]);
        rest += a[i];
        while (pq.size() && rest > 0) {
            int x = pq.top();
            pq.pop();
            rest -= x;
        }
        if (rest > 0) return -1;
    }
    return n - (int)pq.size();
}

rahlin's code

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pb push_back
#define mk make_pair
#define F first
#define S second
using namespace std;

const int INF = 2e18, MAXN = 1e6 + 5, M = 1e9 + 7;
int n, k, a[MAXN], b[MAXN], t[MAXN], ans = 0;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    for (int i = 0; i < k; i++) cin >> t[i];
    sort(t, t + k);

    int lb = -1;
    for (int i = 0; i < k; i++) {
        priority_queue<int> pq;
        int rb = t[i] - 1, l = t[i] - 1;
        pq.push(b[rb]);
        while (l > lb && pq.size()) {
            int f = pq.top();
            pq.pop();
            ans++;
            while (l > lb && f >= 0) {
                if (f >= a[l]) {
                    f -= a[l];
                    a[l] = 0;
                    l--;
                    if (l > lb) pq.push(b[l]);
                } else {
                    a[l] -= f;
                    f = 0;
                    break;
                }
            }
        }
        if (l != lb) {
            cout << -1 << "\n";
            exit(0);
        }
        lb = rb;
    }
    cout << ans << "\n";
}

/*
5 2
1 2 3 4 5
1 1 1 1 1
2
4

5 3
5 4 3 2 1
4 8 7 6 3
1
3
5
*/

TCIRC d053: Q-4-8. 先到先服務 (*)

有 $n$ 個人要依次分配到 $m$ 個櫃台被服務，第 $i$ 個人占用 $t_{i}$ 的時間。求最短時間完成所有人的服務

$n, m \leq 2 \times 10^{5}, t_{i} \leq 10^{4}$

code

#include <iostream>
#include <queue>
using namespace std;

signed main() {
    long long int N, M, t, ot, ans;
    priority_queue<long long int, vector<long long int>, greater<long long int>> pq;
    cin >> N >> M;
    for(int i = 0; i < M; i++) pq.push(0);
    for(int i = 0; i < N; i++){
        cin >> t;
        ot = pq.top();
        pq.pop();
        pq.push(ot + t);
        // 加入目前最空的櫃台
    }
    while(pq.size()){
        ans = pq.top();
        pq.pop();
    }
    // 取最大的
    cout << ans << endl;
}

洛谷 P3419 [POI2005]SAM-Toy Cars

有 $n$ 個不同的玩具，而地上只能放最多 $k$ 個玩具。如果玩具不在地上，則要從架子上拿，如果此時地板上的玩具已經達到了 $k$ 個，則還要拿一個玩具放回架子。依次想拿編號為 $a_{1}, \dots, a_{m}$ 的玩具，求一種安排方式使從架子上拿玩具的次數最少。

$1 \leq k, n, m \leq 10^{5}, 1 \leq a_{i} \leq n$

思路

貪心的用 pq 去維護下次出現的 index，越後面才出現的 toy 可以先放上去

注意到實作的部分若當前的 toy 已經在地板上了那他永遠也出不去 pq (因為每一輪都會有一個東西被 push 進來，而該東西一定比較大)

參考博客的小技巧，我們直接將 k++ 即可解決

code

void solve () {
    cin >> n >> k >> p;
    for (int i = 1; i <= p; ++i)
        cin >> req[i];
    for (int i = p; i; --i) {
        nxt[i] = ((pos[req[i]]) ? pos[req[i]] : (p + 1));
        pos[req[i]] = i;
    }

    priority_queue<pii> pq;

    for (int i = 1; i <= p; i++) {
        if (!inq[req[i]]) {
            if (pq.size() == k) {
                inq[pq.top().id] = false;
                pq.pop();
            }
            pq.push(pii (nxt[i], req[i]));
            inq[req[i]] = true;
            ans++;
        } else {
            k++;
            pq.push(pii (nxt[i], req[i]));
        }
    }

    cout << ans << "\n";
}

2021 TOI pB. 掃地機器人 30%

$n$ 間教室，一開始你在第一間，給你 $T$ 分鐘的打掃時間每間教室第一分鐘可以吸到 $s_{i}$ 的灰塵，每分鐘遞減 $d_{i}$ 個灰塵，從第 $i$ 間教室移動到第 $i + 1$ 間教室花 $t_{i}$ 的時間，問這 $T$ 分鐘最多可以掃到多少灰塵

$n \leq 1000, m \leq 1000, 0 \leq t_{i}, d_{i} \leq 10^{9}, 1 \leq s_{i} \leq 10^{9}$

思路 1 (from APCSC)

反悔法，時間如果夠就都掃，再靠反悔堆把之前的決策反悔掉

code

#include <iostream>
#include <queue>
#define MAXN 100000
using namespace std;

int s[MAXN], d[MAXN], t[MAXN];

int main() {
    long long T, n;

    cin >> n >> T;

    for (int i = 1; i < n; i++) cin >> t[i];
    for (int i = 0; i < n; i++) cin >> s[i];
    for (int i = 0; i < n; i++) cin >> d[i];


    long long ans = 0, cur = 0;
    priority_queue<int, vector<int>, greater<int> > pq;
    for (int i = 0; i < n; i++) {
        T -= t[i];
        while (T < 0 && !pq.empty()) {
            cur -= pq.top();
            pq.pop();
            T++;
        }
        while (t > 0 && s[i] > 0) {
            cur += s[i];
            pq.push(s[i]);
            s[i] -= d[i];
            T--;
        }
        while (!pq.empty() && s[i] > pq.top()) {
            cur += s[i] - pq.top();
            pq.pop();
            pq.push(s[i]);
            s[i] -= d[i];
        }
        ans = max(ans, cur);
    }
    cout << ans << '\n';
}

思路 2 (from twpca)

將每一分鐘貪心地分給目前蒐集得到灰塵量最大的教室就好

code

// 扣掉移動時間後，有 k 分鐘打掃前 e 個教室最大蒐集灰塵量
long long collect_dust(int e, int k) {
    priority_queue<pair<int, int>> pq;  // 維護 (目前蒐集得到的灰塵量, 教室id)
    long long result = 0;

    for (int i = 1; i <= e; i++) {
        pq.emplace(s[i], i);
    }
    for (int t = 1; t <= k; t++) {
        if (pq.empty()) break;  // 所有 >= 0 的灰塵都被掃完了

        auto [dust, classroom] = pq.top();
        pq.pop();

        result += dust;
        if (dust - d[classroom] > 0) {  // 下一次掃除的灰塵量 > 0 的話
            pq.emplace(dust - d[classroom], classroom);
        }
    }
    return result;
}

Zerojudge c835. 背包問題

給你 $n$ 個物品，背包重量限制為 $2^{W}$ ，每個物品的重量是 $2^{w_{i}}$ ，價值是 $v_{i}$ ，求能放到背包內的最大價值和

$n \leq 10^{6}, W, w_{i} \leq 20, v_{i} \leq 10^{9}$

思路

想法 $2^{n - 1} + 2^{n - 1} \leq 2^{n}$
把大的倆倆合併

code

void solve() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        int w, v;
        cin >> w >> v;
        if (w <= m) {
            pq[w].push(v);
        }
    }
    for (int i = 0; i < m; ++i) {
        while(!pq[i].empty()) {
            if(pq[i].size() == 1) {
                pq[i + 1].push(pq[i].top());
                break;
            }
            ll a = pq[i].top();
            pq[i].pop();
            ll b = pq[i].top();
            pq[i].pop();
            pq[i + 1].push(a + b);
        }
    }
    cout << pq[m].top() << "\n";
}

CF 3 D. Least Cost Bracket Sequence

給一個長度為 $n$ ，由 (，) 以及 ? 構成的字串，將第 $i$ 個 '?' 變左括號花費 $a_{i}$ ，變成右括號花費 $b_{i}$ 。將字串中的 ? 都替換掉，問使字串是合法括號的最少花費

$n \leq 5 \times 10^{4}, 1 \leq a_{i}, b_{i} \leq 10^{6}$

思路

默認所有問號為右括號，當前的左括號數小於右括號時，則從之前找到代價最小的問號變成的右括號代替即可

code

#include <bits/stdc++.h>
#define F first
#define S second
#define int long long

using namespace std;
using pii = pair<int, int>;

signed main() {
    string s;
    cin >> s;
    int n = s.size();

    priority_queue<pii, vector<pii>, greater<pii>> pq; 
    int l = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '(') {
            l++;
            continue;
        } else {
            if (s[i] == '?') {
                int a, b;
                cin >> a >> b;
                pq.push({a - b, i});
                s[i] = ')';
                ans += b;
            }
            if (--l < 0) {
                if (pq.empty()) {
                    cout << "-1" << '\n';
                    exit(0);
                }
                ans += pq.top().F;
                s[pq.top().S] = '(';
                l += 2;
                pq.pop();
            }
        }
    }
    if (l) {
        cout << "-1" << '\n';
        exit(0);
    }
    cout << ans << '\n' << s << '\n';
} 

TOI 2021 二模 pC. 配對問題（Pairing）

給定一個序列 $a_{1}, a_{2}, . . ., a_{n}$ ，一個點只能被匹配最多一次，當兩個點 $i$ 與 $j$ 配對時，就會獲得 $a_{i} + a_{i + 1} + \dots + a_{j}$ 的分數。任何配對都不能出現部份相交的情形。匹配結束後，所有沒有被匹配到的點 $i$ ，如果 $a_{i} > 0$ ，可以獲得 $a_{i}$ 分。問分數最大是多少

$1 \leq n \leq 10^{5}, - 10^{9} \leq a_{i} \leq 10^{9}$

思路

【區間 dp : O(n^3)】

dp(l, r) : l ~ r 的最多 cost

dp(l+1, r) + a[l]
dp(l, r-1) + a[r]
切兩半 dp(l, k) + dp(k+1, r)
l 和 r 配對 dp(l+1, r-1) + (a[l]+...+a[r])

【前綴 dp : O(n^2)】

dp(i, k) : 1~i 的 (#左括號 - #右括號) = k

ans = dp(n, 0)

轉移

i 是 "(" : dp(i-1, k-1) - pre[i-1]
i 是 ")" : dp(i-1, k+1) + pre[i]
i 是 "X" : dp(i-1, k) + pre[i] - pre[i-1]

【Greedy 觀察性質, 後悔法: O(n log n)】

我們其實可以用一個 max heap 來維護括號去配對，我們每次將當前向當作右括號，看與 heap 的頂端的和是否能產生正的貢獻，可以的話我們就將右括號的貢獻加上一個負號，並加入 heap 中，代表著之後可以將當前的右括號消除。否則我們就將當前項作為左括號的貢獻加入 heap 中。那麼要如何處理「不選」的貢獻呢? 我們其實可以先把答案加上 sum(a[i])，再將有選的貢獻中加入 -a[i]，這樣就只要處理有選的部份了。我們還要注意一點就是當某一項做了右括號後，又被更後面的右括號取代，我們還是可以用左括號的方式去選他，因為當時他只是因為做右括號產生貢獻才去選的，不代表他不能作左括號。不用怕做右括號的貢獻還沒 pop 出來，左括號的貢獻就已經先出來，因為同時在某一項又做左括號，又做右括號，貢獻一定是負的

這邊提供一組範例

        i         1   2   3  4  5  6  7  8
        a[i]:     3  -1  -5  3  8  4 -3  4
        pre[i]:   3   2  -3  0  8 12  9 13

參考自 : TOI 2021 Solutions - p3 pairing

code

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
const int maxn = 100025;
template <typename T> using max_heap = priority_queue<T, vector<T>, less<T>>;
int a[maxn];
long long pre[maxn];
signed main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) pre[i] = pre[i-1] + a[i];

    max_heap<long long> pq;
    long long ans = 0;
    for (int i = 1; i <= n; i++) ans += max(a[i], 0);
    for (int i = 1; i <= n; i++) {
        long long lbraceValue = -pre[i-1] - max(a[i], 0);
        long long rbraceValue = pre[i] - max(a[i], 0);
        if (!pq.empty() && rbraceValue + pq.top() > 0) {
            ans += rbraceValue + pq.top(), pq.pop();
            pq.push(lbraceValue);
            pq.push(-rbraceValue);
        } else {
            pq.push(lbraceValue);
        }
    }
    cout << ans << '\n';
}

CF 1821 E. Rearrange Brackets

對於一個合法的括號序列，定義它的「cost」為進行若干次以下操作，將它清空的最小總代價: 選取兩個相鄰的左右括號刪除，並將代價加上原右括號右邊的括號數量。

你可以進行不超過 k 次以下操作，將給定的匹配括號序列 s 變為另一個匹配括號序列: 選取一個括號，將它移動到序列的任意位置。求最終括號字串的「cost」的最小值

$| s | \leq 2 \times 10^{5}, 0 \leq k \leq 5$

思路

當注意到最優決策時，是從右邊開始進行括號匹配，而每對括號的貢獻是括號內的括號數量 / 2

而 k 次的操作就可以視為將 k 個貢獻最大的括號的貢獻給移除，因為這些括號貢獻會最大就代表我們一定能把它照貢獻大到小看，對於每組移動到不會影響別人的位置（不會對別人造成貢獻），所以就用 prioirty queue 維護每組的貢獻即可

code

#include <bits/stdc++.h>
#define int long long

using namespace std;

void solve() {
    int k;
    cin >> k;
    string s;
    cin >> s;

    int n = s.size();
    priority_queue<int> pq;
    vector<int> stk;
    int cost = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '(') {
            cost += stk.back() - i - 1;
            pq.push(stk.back() - i - 1);
            stk.pop_back();
        } else {
            stk.push_back(i);
        }
    }
    while (pq.size()) {
        if (k == 0) break;
        k--;
        cost -= pq.top();
        pq.pop();
    }
    cout << cost / 2 << '\n';
}

signed main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
} 

2020 全國賽 D. 水果包裝

有 $n$ 個水果，第 $i$ 個的重量是 $w_{i}$ ，然後機器會按照 $p_{1}, \dots, p_{n}$ 的順序將水果裝袋。有 $m$ 個袋子，機器在裝某個水果時，會把它放到總重最小的那個袋子裡，如果有等重的會放到編號最小的那個裡面。

已知全部裝完後，第 $i$ 個袋子裡的水果有哪些，求 $p_{1}, \dots, p_{n}$ ，或者說無解。

$n \leq 2 \times 10^{5}, 1 \leq w_{i} \leq 10^{9}$

思路

第一個選的一定是從最輕的且編號最小的，也就是從第一個袋子裡面的選。而要讓第一個袋子的其他水果之後有辦法被選到，先把最小的選出來最合適，把它移除掉後，再來就是子問題。所以我們可以用 priority queue 維護每個袋子的 (剩餘重量, 編號)，對於每個袋子也用 priority queue 維護剩下的物品的重量，越小的越先被 pop 出來，如果沒東西可 pop 就代表無解

更詳細可參考 : twpca editorial twpca code

CF 1821 D. Black Cells

有一個數線，給 n 個不相交的 interval，代表只能在這些 interval 內的點塗色，目標是將 k 個點塗色。每次可做以下操作:

往右移一格
將 shift 按住（在一個點上若 shift 被按住即塗色）
將 shift 鬆開

問最少幾次操作可至少將 k 個點塗色

$n \leq 2 \times 10^{5}, 1 \leq k \leq 10^{9}, 1 \leq l_{i}, r_{i} \leq 10^{9}$

思路

考慮觀察性質可知答案只和右端點大小以及所選的區間數量有關。甚至可以直接寫出計算式:

ans = 覆蓋的區間數量 * 2 + end

其中 end = 最後塗色的點，例如說 interval 有 [1, 1], [3, 5] 而 k = 3，那我們只需要塗 [1, 1], [3, 4] 就好，end = 4。但我們不確定要覆蓋哪些區間，我們可以使用反悔貪心，枚舉當 end 的 interval，將 interval 用長度加入至 min heap 內，若當前 heap 內的被 interval 覆蓋到的點數量 >= k 則 pop 最小長度的 interval，並順便計算當前的答案，跟真正的答案取 min

code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 5;
int l[N], r[N], n, k;

void solve() {
    priority_queue<int, vector<int>, greater<int>> q;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> l[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> r[i];
    }
    int num = 0, sum = 0, ans = INT_MAX;
    for (int i = 1; i <= n; i++) {
        q.push(r[i] - l[i] + 1);
        num++;
        sum += r[i] - l[i] + 1;
        while (q.size() && sum >= k) {
            ans = min(ans, r[i] - (sum - k) + num * 2);
            sum -= q.top();
            q.pop();
            num--;
        }
    }
    if (ans == INT_MAX) {
        cout << "-1\n";
        return;
    } else {
        cout << ans << '\n';
    }
}

signed main() {
    int t; 
    cin >> t;
    while (t--) {
        solve();
    }
}

CSES Room Allocation

有 $n$ 人，給每個人的入住時間與離開時間 $[l_{i}, r_{i}]$ ，問至少要幾間房間才夠，並輸出每個人的房間編號

$n \leq 2 \times 10^{5}, 1 \leq l_{i} \leq r_{i} \leq 10^{9}$

思路

用 min heap 維護每個人的 $r_{i}$ ，有人要住進來時就住進當前 $r_{i}$ 最小的房間，若那個人還沒離開就再開一間新的即可

code

#include <bits/stdc++.h>
#define int long long

using namespace std;
using pii = pair<int, int>;

struct Interval {
    int l, r, id;

    bool operator<(const Interval &rhs) const {
        return l < rhs.l;
    }
};

const int INF = 9e18;
const int MAXN = 2e5 + 5;
int n, k, ans[MAXN];

signed main() {
    cin >> n;
    vector<Interval> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].l >> a[i].r;
        a[i].id = i;
    }
    sort(a.begin(), a.end());

    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({a[0].r, 1});
    ans[a[0].id] = 1;
    int cnt = 1;
    for (int i = 1; i < n; i++) {
        auto [t, room] = pq.top();
        if (t < a[i].l) {
            pq.pop();
            pq.push({a[i].r, room});
            ans[a[i].id] = room;
        } else {
            pq.push({a[i].r, ++cnt});
            ans[a[i].id] = cnt;
        }
    }
    cout << cnt << '\n';
    for (int i = 0; i < n; i++) {
        cout << ans[i] << " ";
    }
}

POI 2012 HUR-Warehouse Store

有 $n$ 天，第 $i$ 天先進貨 $a_{i}$ 個，然後會有要賣出 $b_{i}$ 個的訂單，問最多可以接多少個訂單

$n \leq 2.5 \times 10^{5}, 0 \leq a_{i}, b_{i} \leq 10^{9}$

思路

寫多這種題目大概就會知道他的套路，從第一天開始，如果能賣出去我們就賣，假設我們要賣 $b_{i}$ ，不能賣的時候我們可以從之前賣出去的那些訂單挑 $b$ 值最大的，假設是 $b_{j}$ ，看如果放棄那個改買我們目前的訂單是否更優，也就是看 $b_{j}$ 是否 $> b_{i}$ ，是的話就放棄 $b_{j}$ ，轉買 $b_{i}$ 。這個可以用 max heap 來維護。

code

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, ans;
int a[300010], b[300010];
bool vis[300010];
priority_queue<pair<int, int>, vector<pair<int, int> > > q;  // 维护一个大根堆

signed main() {
    scanf("%lld", &n);
    int rest = 0;
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for (int i = 1; i <= n; i++) scanf("%lld", &b[i]);
    for (int i = 1; i <= n; i++) {
        rest += a[i];
        if (b[i] <= rest) {
            ans++;
            q.push(make_pair(b[i], i));
            rest -= b[i]; 
            vis[i] = 1;
        } else if (!q.empty() && b[i] < q.top().first) {
            int j = q.top().second;
            q.pop(); 
            rest += b[j];
            rest -= b[i];
            vis[j] = 0, vis[i] = 1; 
            q.push(make_pair(b[i], i));
        }
    }
    printf("%lld\n", ans);
    for (int i = 1; i <= n; i++)
        if (vis[i]) printf("%d ", i);
    return 0;
}

USACO 2016 OPEN Landscaping P

有 $n$ 個花壇，第 $i$ 個花壇目前有 $a_{i}$ 單位的泥土，需要 $b_{i}$ 單位的泥土。可以做以下操作，問最小花費是多少：

將指定的花壇的泥土加一單位，花費 $x$
將指定的花壇的泥土移走一單位，花費 $y$
從第 $i$ 個花壇運一單位的泥土到第 $j$ 個花壇，花費 $z | i - j |$

$n \leq 10^{5}, 0 \leq a_{i}, b_{i} \leq 10, 0 \leq x, y \leq 10^{8}, 0 \leq z \leq 1000$

思路

由於增加、刪除和移動泥土的操作都是基於單個單位的泥土進行的，而且泥土範圍 $1 \leq a_{i}, b_{i} \leq 10$ 非常小，我們簡化問題，單獨考慮每一個泥土單位：

對於每單位泥土在第 $i$ 個位置上，設處理該單位泥土的花費為 $v_{i}$ 費用，答案就是 $\sum v_{i}$ 。對於第 $i$ 個花壇，如果它現在缺土（ $a_{i} < b_{i}$ ），則可以直接購進一個單位的泥土，花費為 $x$ ，或是若第 $j < i$ 個花壇多了土，可以從它那裡拿一份過來，花費為 $v_{i} = z | i - j | - v_{j}$ ，其中 $v_{j}$ 是花壇 $j$ 那份土的花費，需要減掉避免算多（反悔）；最終花費為 $v_{i} = min {x, z | i - j | - v_{j}}$ ；

同理，若第 $i$ 個花壇現在多土（ $a_{i} > b_{i}$ ），則可以直接刪除一個單位的泥土，花費為 $y$ ，或是若第 $j < i$ 個花壇缺了土，可以移一份給它，花費為 $v_{i} = z | i - j | - v_{j}$ ；最終花費為 $v_{i} = min {y, z | i - j | - v_{j}}$ 。

我們考慮化簡移土花費：

\begin{aligned} v_{i} & = z | i - j | - v_{j} (i > j) \\ = z i - z j - v_{j} \\ = z i + (- z j - v_{j}) \end{aligned}

注意到 $(- z j - v_{j})$ 是只關於之前位置泥土的信息，且 $(- z j - v_{j})$ 越小，總花費越小；所以我們可以給多的泥土和少的泥土分別開一個大根堆記錄這個信息，每次遍歷到新泥土時比較是直接購進、刪除還是和之前的泥土移動便宜，本質上就是反悔貪心，時間複雜度 $O (n \log n)$ 。具體 heap 內要插入什麼，假設現在已經處理完 $i$ ，我們就把 $(- i z - v_{i})$ 存進堆裡，供後面的答案更新。

code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 5;
int v[N], a[N], b[N];
priority_queue<int, vector<int>, greater<int>> pq1, pq2;

signed main() {
    int n, x, y, z;
    cin >> n >> x >> y >> z;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        for (int j = 1; j <= a[i] - b[i]; j++) {
            v[i] = y;
            if (!pq1.empty()) {
                v[i] = min(v[i], i * z + pq1.top());
                pq1.pop();
            }
            pq2.push(-v[i] - i * z);
            ans += v[i];
        }
        for (int j = 1; j <= b[i] - a[i]; j++) {
            v[i] = x;
            if (!pq2.empty()) {
                v[i] = min(v[i], i * z + pq2.top());
                pq2.pop();
            }
            pq1.push(-v[i] - i * z);
            ans += v[i];
        }
    }
    cout << ans << '\n';
}

老鼠进洞 2022 全國賽 pB. . 自行車歸位 (bicycle) / UOJ #455. 【UER #8】雪灾与外卖

有 $n$ 隻老鼠，座標分別為 $x_{i}$ ，有 $m$ 個洞，有座標 $y_{i}$ ，代價 $w_{i}$ ，容量 $c_{i}$ 。老鼠 $i$ 進洞 $j$ 的代價為 $| x_{i} - y_{i} | + w_{i}$ 。每隻老鼠必須進洞。

$2 \leq n, m \leq 10^{5}, 0 \leq x_{i}, y_{i}, c_{i}, w_{i} \leq 10^{9}$

思路

結論一：配對不會交叉。
結論二：對於一組匹配，老鼠和洞不會同時反悔。 (由左往右進行匹配，同時反悔會產生交叉)

【加入老鼠，座標 x】

在Q1中取出代價最少的，設代價為 $v$ ，答案為 $w = x + v$ （這裡的 $v$ 顯然是負數）

老鼠反悔，配對更後面的洞：在Q0中加入 $- w + v$ 。

但是此時洞不能反悔因為不然的話當前這個老鼠就無法匹配了。

【加入洞，座標 x，代價 cost，容量 c】

在容量被耗盡或老鼠的代價不是負數時（這樣的話必然是不優），重複從 Q0 中取出代價最少的老鼠，設這個代價為 $v$ 。答案加上 $w = v + x + c o s t$ 。

老鼠反悔，配對更後面的洞: 在 Q0 中加入 $- w + v$ 的老鼠
洞反悔，配對後的老鼠: 在Q1 中加入 $- w - x + v$ 的洞

可以洞反悔? 這是因為如果這個時候洞反悔了拋棄了這個老鼠相當於老鼠保持了原來的匹配，依舊能讓每個老鼠都進洞

實際上兩種操作在後面不可能都發生，否則匹配相交。注意到 Q0 老鼠進堆的複雜度沒有保障，我們發現老鼠反悔的代價都是 $- w + v = - x - c o s t$ 。也就是說每次一個洞都匹配了若干不同的老鼠後，往老鼠堆裡面丟的東西都是等權的，因此只需要丟一次就行了

code

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define ll long long
#define INF 2000000000
int n, m;
ll X[N];
ll Y[N], W[N], C[N];
ll ans;

struct info {
    ll v, cnt;
};  

bool operator<(info a, info b) {
    return b.v < a.v;
}

priority_queue<info> q0, q1;  
void ins0(ll x) {
    info t = q1.top();  
    q1.pop();
    ans += x + t.v;
    if (--t.cnt)  
        q1.push(t);
    q0.push((info){-(x + t.v) - x, 1});
}

void ins1(ll x, ll cost, ll c) {
    ll s = 0;
    while (c && !q0.empty()) {
        info t = q0.top();
        if (cost + x + t.v >= 0) 
            break;
        q0.pop();
        ll mn = min(t.cnt, c);
        ans += (cost + x + t.v) * mn;
        q1.push((info){-(cost + x + t.v) - x + cost, mn});
        s += mn;
        t.cnt -= mn;
        c -= mn;
        if (t.cnt)
            q0.push(t);
    }
    if (c) q1.push((info){-x + cost, c});  
    if (s) q0.push((info){-cost - x, s}); 
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%lld", &X[i]);
    ll sum = 0;
    for (int i = 1; i <= m; ++i) scanf("%lld%lld%lld", &Y[i], &W[i], &C[i]), sum += C[i];
    if (sum < n) {
        printf("-1\n");
        return 0;
    }
    q1.push((info){INF, INF});
    int i = 1, j = 1;
    while (i <= n || j <= m)  // 保证老鼠和窝的相对位置
        if (i <= n && (j > m || X[i] < Y[j]))
            ins0(X[i]), i++;
        else
            ins1(Y[j], W[j], C[j]), j++;
    printf("%lld\n", ans);
    return 0;
}

reference