[JSOI2007]建筑抢修【每日一题】5月26日

一.题目链接

$\quad$ [JSOI2007]建筑抢修

二.题目大意

$\quad$ n 个物品，每个物品有修理时间 t1，截止时间 t2，只有修完物品后时间仍未超过截止时间才算成功修理.

$\quad$ 求最多能成功修理多少件物品.

三.分析

$\quad$ 很经典的优先队列时光倒流大法贪心（口胡

$\quad$ 首先对截止时间排序，建立大根堆（优先队列），对 n 件物品从前到后依次扫描，如果当前物品可成功修理，那就修理，并把其修理时间放到大根堆中；否则，如果当前物品的修理时间小于大根堆的根，那就互换这两件物品.

$\quad$ 简单来说就是：能修则修；不能修则尝试找一个之前修理过且最差的物品，与当前物品替换，因为这样操作后，答案不会变差而且总的花费时间减少.

四.代码实现

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

typedef long long ll;

const int M = (int)150000;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;

struct node
{
    ll t1, t2;
}s[M + 5];

bool cmp(node a, node b)
{
    return a.t2 < b.t2;
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int n; scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%lld %lld", &s[i].t1, &s[i].t2);
    sort(s + 1, s + n + 1, cmp);
    priority_queue <ll> q;
    ll t = 0; int ans = 0;
    for(int i = 1; i <= n; ++i)
    {
        if(t + s[i].t1 <= s[i].t2) q.push(s[i].t1), t += s[i].t1, ++ans;
        else if(s[i].t1 < q.top()) t -= q.top(), q.pop(), t += s[i].t1, q.push(s[i].t1);
    }
    printf("%d\n", ans);
    return 0;
}