M_sea

洛谷4053 [JSOI2007]建筑抢修
LuoguBZOJ分析考虑一个贪心。先按$t_2$从小到大排序,考虑每一个建筑能否在$t_2$前修好。如果可以,就...
扫描右侧二维码阅读全文
11
2019/01

洛谷4053 [JSOI2007]建筑抢修

Luogu

BZOJ

分析

考虑一个贪心。

先按$t_2$从小到大排序,考虑每一个建筑能否在$t_2$前修好。

如果可以,就将当前时间加上$t_1$。

如果不行,就在所有修好的建筑中找到一个最大的$t_1$,并与当前的$t_1$作比较,如果当前更小则替换成当前的建筑。

用一个堆来维护$t_1$即可。

正确性比较显然?反正我不会证就是了。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=150000+10;

struct Building { int t1,t2; };
Building a[N];
inline int cmp(const Building& a,const Building& b) {
    return (a.t2<b.t2)||(a.t2==b.t2&&a.t1<b.t1);
}
priority_queue<int> Q;

int main() {
    int n=read();
    for (re int i=1;i<=n;++i) a[i].t1=read(),a[i].t2=read();
    sort(a+1,a+n+1,cmp);
    ll t=0; int ans=0;
    for (re int i=1;i<=n;++i) {
        if (t+a[i].t1<=a[i].t2)
            ++ans,t+=(ll)a[i].t1,Q.push(a[i].t1);
        else {
            int mx=Q.top();
            if (mx>a[i].t1) {
                t-=(ll)mx,Q.pop();
                t+=(ll)a[i].t1,Q.push(a[i].t1);;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 01 月 23 日 01 : 05 PM

发表评论