CF436E Cardboard Box 题解

题意：

每个玩过《Cut the Rope》的人都很清楚游戏的玩法。游戏中的所有关卡都分为多个盒子。最初只有一个包含一些关卡的盒子是可用的。玩家需要通过完成关卡来获得星星，收集星星可以解锁包含新关卡的盒子。

假设你是第一次玩《Cut the Rope》。目前你只有第一个盒子的关卡（顺便说一句，它被称为“纸箱盒”）。每个关卡有两个整数特征：\(a_{i}\) — 完成该关卡以获得一颗星所需的时间，\(b_{i}\) — 完成该关卡以获得两颗星所需的时间（\(a_{i} < b_{i}\)）。

你想尽快打开下一个盒子。因此，你需要至少获得 \(w\) 颗星。如何实现这一目标？注意，每个关卡只能通过一次：要么获得一颗星，要么获得两颗星。不一定需要通过所有关卡。

省流：

\(n\) 个关卡，对每个关卡，你可以花 \(a_i\) 代价得到一颗星，也可以花 \(b_i\) 代价得到两颗星也可以不玩。

问获得 \(w\) 颗星最少需要多少时间。保证 \(a_i < b_i\) 。

输入格式：

第一行包含两个整数 \(n\) 和 \(w\) \((1 \leq n \leq 3 \cdot 10^{5},~1 \leq w \leq 2n)\)

表示第一个盒子中的关卡数量和打开另一个盒子所需的星星数量。

接下来的 \(n\) 行每行包含两个整数 \(a_{i}\) 和 \(b_{i}\) \((1 \leq a_{i} < b_{i} \leq 10^{9})\) 表示第 \(i\) 个关卡的属性。

输出格式：

第一行输出一个整数 \(t\) — 打开下一个盒子所需的最短时间。

第二行输出 \(n\) 个数字，不带空格 — 最优方案的描述：

如果你需要通过第 \(i\) 个关卡以获得一颗星，第 \(i\) 个数字应为 1；

如果你需要通过第 \(i\) 个关卡以获得两颗星，第 \(i\) 个数字应为 2；

如果你不需要通过第 \(i\) 个关卡，第 \(i\) 个数字应为 0。

考虑如何从选了 \(i\) 颗星的最优方案拓展到选了 \(i+1\) 颗星的最优方案：

选择一个没有选的位置 \(i\) ，花 \(a_i\) 选一颗星。
选一个选了一颗星的位置 \(i\) ，花 \(b_i-a_i\) 选两颗星。
选一个选了一颗星的位置 \(i\) 和一个没选的位置 \(j\) ，花 \(b_j-a_i\) 改成 \(i\) 不选， \(j\) 选两颗。
选一个选了两颗星的位置 \(i\) 和一个没选的位置 \(j\) ，花 \(b_j-(b_i-a_i)\) 改成 \(i\) 不选，\(j\) 选两颗。

考虑用 5 个小根堆维护 \((a_i),\ (b_i-a_i),\ (-a_i),\ (b_i),\ -(b_i-a_i))\) 。

注意我们每次决策的时候可能会改变一个位置的决策，这个时候堆里的一些元素就无效了

可以在每次拿堆顶元素的时候判断一下它的 Type 和所在位置的 Type 是否一致，不一致就扔掉继续拿。

时间复杂度 \(\mathcal{O}(n\log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(3e5 + 15))

int a[N], b[N], ans[N];
struct node { int x, i; };
bool operator<(const node &x, const node &y) { return x.x > y.x; }
struct qwq
{
    int op; priority_queue<node> q;
    void up(){ while(!q.empty() && ans[q.top().i] != op) q.pop(); }
    void push(const node &x) { q.push(x); }
    node top() { up(); return q.top(); }
    bool empty() { up(); return q.empty(); }
} q1, q2, q3, q4, q5;
void push1(int x) { ans[x] = 1; q2.push({b[x] - a[x], x}); q3.push({-a[x], x}); }
void push2(int x) { ans[x] = 2; q5.push({-(b[x] - a[x]), x}); }
void push0(int x) { ans[x] = 0; q1.push({a[x], x}); q4.push({b[x], x}); }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m, res = 0; cin >> n >> m; rep(i, 1, n) cin >> a[i] >> b[i];
    q1.op = q4.op = 0; q2.op = q3.op = 1; q5.op = 2;
    rep(i, 1, n) { q1.push({a[i], i}); q4.push({b[i], i}); }
    rep(i, 1, m)
    {
        int x, p, q, mn = INF, op = -1;
        if(!q1.empty() && (x = q1.top().x) < mn) { mn = x; p = q1.top().i; op = 1; }
        if(!q2.empty() && (x = q2.top().x) < mn) { mn = x; p = q2.top().i; op = 2; }
        if(!q3.empty() && !q4.empty() && (x = q3.top().x + q4.top().x) < mn) { mn = x; p = q3.top().i; q = q4.top().i; op = 3; }
        if(!q5.empty() && !q4.empty() && (x = q5.top().x + q4.top().x) < mn) { mn = x; p = q5.top().i; q = q4.top().i; op = 4; }
        res += mn; if(op == -1) exit(1);
        else if(op == 1) push1(p);
        else if(op == 2) push2(p);
        else if(op == 3) { push0(p); push2(q); }
        else if(op == 4) { push1(p); push2(q); }
    }
    cout << res << '\n'; rep(i, 1, n) cout << ans[i];
    return 0;
}