建筑抢修

洛谷-P4053-建筑抢修

分析

可以反悔的贪心。

实现

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 150010;
struct node {
    LL c, d; // 花费、截止时间
    bool operator < (const node& o) const {
        return c < o.c; // 大顶堆
    }
};
int n;
node a[N];
priority_queue<node> pq;

bool cmp (const node& a, const node& b) {
    return a.d < b.d;
}

int main () {
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> a[i].c >> a[i].d;

    sort(a + 1, a + n + 1, cmp);
    LL res = 0, t = 0;
    for (int i = 1; i <= n; ++ i) {
        int c = a[i].c, d = a[i].d;
        if (t + c <= d) { // 来得及
            ++ res;
            t += c;
            pq.push(a[i]);
        } else if (!pq.empty() && c < pq.top().c) {
            t += c - pq.top().c;
            pq.pop();
            pq.push(a[i]);
        }
    }
    cout << res << endl;
    return 0;
}