(luogu4053)[JSOI2007]建筑抢修

发表于 | 分类于 ，

原题链接

思路:

根据直觉, 首先需要考虑报废时间较前的, 但这样很有可能因为前面的修复时间太长而无法修复后面的建筑.

所以需要考虑第二个贪心方案: 若当前建筑无法修复, 但如果放弃已经修复的建筑中修复时间最长的建筑后可以修复, 且该建筑的修复时间小于这个放弃修复的建筑时, 可以将这个放弃修复的建筑替换为当前建筑.

原因很简单: 两个建筑二选一时选择修复用时较短的那个建筑可以给后面的建筑省下更多的时间修复.

使用大根堆存储之前已修复建筑的修复时间即可.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int Mn(150500);
typedef long long LL;
struct Str {
    LL x,y;
    bool operator < (const Str& rhs) const {    //重载运算符以排序
        return y==rhs.y ? x<rhs.x : y<rhs.y;
    }
}a[Mn];

int main() {
    int n;
    scanf("%d",&n);
    for(int i(1);i<=n;++i) {
        scanf("%lld %lld",&a[i].x,&a[i].y);
    }
    sort(a+1,a+n+1);    //贪心策略1
    priority_queue<LL> pq;  //大根堆
    LL t(0);
    int ans(0);
    for(int i(1);i<=n;++i) {
        if(t+a[i].x<=a[i].y) {
            t += a[i].x;
            pq.push(a[i].x);
            ++ans;
        } else {
            if(!pq.empty() && t-pq.top()+a[i].x<=a[i].y && a[i].x<pq.top()) {   //贪心策略2
                t -= pq.top()-a[i].x;
                pq.pop();
                pq.push(a[i].x);
            }
        }
    }
    printf("%d",ans);
    return 0;
}