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

· · 题解

题目传送门

前置知识：反悔贪心、堆。

一道十分经典的反悔贪心题。

可以先将每个气球按照最晚的爆炸时间 L_i + D_i 升序排序，这样可以确保之前所有气球的最晚爆炸时间都不晚于当前气球。

对于第 i 个气球，假设前面花费了 s 的时间。如果 s \le L_i + D_i，那么可以直接将该气球吹爆。反之，如果 s > L_i + D_i，则我们需要进行反悔操作，即删掉前面花费时间最长的气球。容易想到可以使用大根堆来维护耗时最长的气球。

上述做法的时间复杂度为 O(n \log n)，可通过本题。

::::info[参考代码]

我就知道你会点进来（x

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

const int N = 3e5 + 10;
priority_queue<int> q;

struct Balloon {
    ll l, d;
    bool operator<(const Balloon& o) const {
        return l + d < o.l + o.d;
    }
} b[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> b[i].l >> b[i].d;
    }
    sort(b + 1, b + n + 1);
    ll sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += b[i].d;
        q.push(b[i].d);
        if (sum > b[i].l + b[i].d) {
            sum -= q.top();
            q.pop();
        }
    }
    cout << q.size() << '\n';
    return 0;
}

::::