A1520 [BJ2020.C2] 装备升级

// A1520 [BJ2020.C2] 装备升级 —— 增广贪心
//
// 每件装备可以升 0/1/2 级：第 i 件从 0 级升到 1 级花 w1_i 枚金币，
// 从 1 级升到 2 级再花 w2_i 枚金币。目标：总共升级 m 次，花费最少。
//
// 做法：从「一件都没升」的状态出发，一次一次地「增广」一个升级次数。
// 每一步在四种候选方案里挑代价最小的那个执行：
//   A：把一件 0 级装备升到 1 级，代价 w1（取 0 级装备里最小的 w1）；
//   B：把一件 1 级装备升到 2 级，代价 w2（取 1 级装备里最小的 w2）；
//   C：把一件 1 级装备降回 0 级（退回 w1），同时把一件 0 级装备一次升到 2 级（花 w1+w2）；
//   D：把一件 2 级装备降回 1 级（退回 w2），同时把一件 0 级装备一次升到 2 级。
// C、D 是「反悔」操作：当某件装备的第二次升级特别便宜时，
// 与其先升别的装备再补它，不如把这件装备直接一次升到 2 级更划算。
//
// 每个候选的最优取值用四个堆维护（懒删除），总复杂度 O(n log n + m log n)。

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

typedef long long ll;
const ll INF = (1LL << 62);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<ll> w1(n), w2(n);
    for (int i = 0; i < n; i++) cin >> w1[i] >> w2[i];

    vector<int> lvl(n, 0);
    // 0 级装备：w1 最小、w1+w2 最小
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> hEmptyW1, hEmptyC;
    // 1 级装备：w2 最小、w1 最大
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> hOneW2;
    priority_queue<pair<ll, int>> hOneW1Max;
    // 2 级装备：w2 最大
    priority_queue<pair<ll, int>> hTwoW2Max;

    auto setLevel = [&](int i, int v) {
        lvl[i] = v;
        if (v == 0) {
            hEmptyW1.push({w1[i], i});
            hEmptyC.push({w1[i] + w2[i], i});
        } else if (v == 1) {
            hOneW2.push({w2[i], i});
            hOneW1Max.push({w1[i], i});
        } else {
            hTwoW2Max.push({w2[i], i});
        }
    };
    for (int i = 0; i < n; i++) setLevel(i, 0);

    ll total = 0;
    for (int step = 0; step < m; step++) {
        // 懒删除：把已经不在该集合里的堆顶弹掉
        while (!hEmptyW1.empty() && lvl[hEmptyW1.top().second] != 0) hEmptyW1.pop();
        while (!hEmptyC.empty() && lvl[hEmptyC.top().second] != 0) hEmptyC.pop();
        while (!hOneW2.empty() && lvl[hOneW2.top().second] != 1) hOneW2.pop();
        while (!hOneW1Max.empty() && lvl[hOneW1Max.top().second] != 1) hOneW1Max.pop();
        while (!hTwoW2Max.empty() && lvl[hTwoW2Max.top().second] != 2) hTwoW2Max.pop();

        ll best = INF;
        int kind = -1, j = -1, i = -1;
        // A：0 级装备升 1 级
        if (!hEmptyW1.empty()) {
            best = hEmptyW1.top().first;
            kind = 0;
            j = hEmptyW1.top().second;
        }
        // B：1 级装备升 2 级
        if (!hOneW2.empty() && hOneW2.top().first < best) {
            best = hOneW2.top().first;
            kind = 1;
            j = hOneW2.top().second;
        }
        // C：1 级降回 0 级，另一件 0 级一次升到 2 级
        if (!hEmptyC.empty() && !hOneW1Max.empty()) {
            ll v = hEmptyC.top().first - hOneW1Max.top().first;
            if (v < best) {
                best = v;
                kind = 2;
                j = hEmptyC.top().second;
                i = hOneW1Max.top().second;
            }
        }
        // D：2 级降回 1 级，另一件 0 级一次升到 2 级
        if (!hEmptyC.empty() && !hTwoW2Max.empty()) {
            ll v = hEmptyC.top().first - hTwoW2Max.top().first;
            if (v < best) {
                best = v;
                kind = 3;
                j = hEmptyC.top().second;
                i = hTwoW2Max.top().second;
            }
        }

        if (kind == 0) {
            setLevel(j, 1);
            total += w1[j];
        } else if (kind == 1) {
            setLevel(j, 2);
            total += w2[j];
        } else if (kind == 2) {
            setLevel(j, 2);
            setLevel(i, 0);
            total += w1[j] + w2[j] - w1[i];
        } else {
            setLevel(j, 2);
            setLevel(i, 1);
            total += w1[j] + w2[j] - w2[i];
        }
    }

    cout << total << '\n';
    return 0;
}