题解：P15699 [2018 KAIST RUN Spring] Touch The Sky

· · 题解

六倍经验！

:::info[题意]{open} 第 i 个气球只能在海拔 \le L_i 时吹起，并将海拔升高 D_i 后并爆炸。每次只能存在一个气球，求最多能炸掉几个气球。 :::

:::info[解法]{open} 显然是个反悔贪心。

考虑先按吹这个气球的最晚爆炸时间排序，即 L_i + D_i，以计算下一个气球的吹起时间。在计算途中，如果当前的时间已经超过吹气球的最晚时间了，就要反悔，去掉浪费海拔最大的气球，这可以用大根堆维护。 :::

:::info[参考实现]{open}

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
using ll = unsigned long long;

constexpr int MAXN = 3e5 + 10;

struct node {
    ll l, r, len;
    inline bool operator < (const node &other) const {return len < other.len;}
} work[MAXN];

int n;

int main() {
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int ans = 0;
    ll sum = 0;
    cin >> n;
    for (register int i = 1; i <= n; ++i) cin >> work[i].l >> work[i].r, work[i].len = work[i].l + work[i].r;
    sort(work + 1, work + 1 + n);
    priority_queue<ll> qwq;

    for (register int i = 1; i <= n; ++i) {
        sum += work[i].r, qwq.push(work[i].r);
        if (sum > work[i].len) sum -= qwq.top(), qwq.pop(); // 如果这个 r 更大，就不用变、刚好弹出，否则就是它的 l 更大，当然能够被容纳，故答案不变
        else ++ans;
    }

    cout << ans;
    return 0;
}

:::