Luogu-P4053

题面

简单来说,你拥有n个破损的建筑,第 $i$ 个建筑需要 $cast_i$的时间才能修好,而如果当前时间超过了$t_i$还没有修好,这个建筑就炸掉了。

现在问你你最多可以修多少建筑

首先想到贪心,按照报废的时间从小到大排序能修就休,但是如果某个建筑的维修时间特别长而报废时间很短,选择了他就无法选择后面的建筑。这种贪心方法很显然存在问题。

那该怎么做呢?考虑带“反悔”的贪心,依旧按照报废时间排序,把每次选择的建筑话费时间加入优先队列。如果对于第$i$建筑剩余的时间不足以维修但堆顶部的时间大于此时间,那么此时反悔(不修堆顶的那个建筑,转而修当前这个。显然会使得花费的时间变小)。

代码:

1
#include <iostream>
2
#include <algorithm>
3
#include <vector>
4
#include <climits>
5
#include <queue>
6
7
using namespace std;
8
using lint = long long;
9
10
struct House {
11
    lint cast;
12
    lint upt;
13
};
14
vector<House> hs;
15
priority_queue<lint> Q;
16
17
int main() {
18
    ios::sync_with_stdio(false);
19
    cin.tie(nullptr);
20
    cout.tie(nullptr);
21
    int n;
22
    cin >> n;
23
    for (int i = 0; i < n; ++i) {
24
        lint c, u;
25
        cin >> c >> u;
26
        hs.push_back(House{c, u});
27
    }
28
    sort(hs.begin(), hs.end(), [](const House & a, const House & b) {
29
        return a.upt < b.upt;
30
    });
31
    lint cast = 0;
32
    int cnt = 0;
33
    for (auto &&h : hs) {
34
        if(cast + h.cast <= h.upt) {
35
            ++cnt;
36
            cast += h.cast;
37
            Q.push(h.cast);
38
        } else {
39
            auto t = Q.top();
40
            if(h.cast < t) {
41
                cast = cast - t + h.cast;
42
                Q.pop();
43
                Q.push(h.cast);
44
            }
45
        }
46
    }
47
    cout << cnt << endl;
48
    return 0;
49
}