P4053 [JSOI2007]建筑抢修 堆贪心

思路：堆贪心

提交：1次

题解：

先按时间(sort)，然后如果能修就直接扔堆里，不能修取堆顶比一下时间长短，把时间短的扔进堆；

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#define ull unsigned long long
#define ll long long
#define R register int
using namespace std; 
#define pause (for(R i=1;i<=10000000000;++i))
#define In freopen("NOIPAK++.in","r",stdin)
#define Out freopen("out.out","w",stdout)
namespace Fread {
static char B[1<<15],*S=B,*D=B;
#ifndef JACK
#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)
#endif
inline int g() {
    R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;
    if(ch==EOF) return EOF; do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;
} inline bool isempty(const char& ch) {return (ch<=36||ch>=127);}
inline void gs(char* s) {
    register char ch; while(isempty(ch=getchar()));
    do *s++=ch; while(!isempty(ch=getchar()));
}
} using Fread::g; using Fread::gs;

namespace Luitaryi {
const int N=150010;
struct node { ll w,t;
    inline bool operator <(const node& that) const {return t<that.t;}
}a[N];
int n,cnt;
ll tot;
priority_queue<ll> q;
inline void main() {
    n=g(); for(R i=1;i<=n;++i) a[i].w=g(),a[i].t=g();
    sort(a+1,a+n+1);
    for(R i=1;i<=n;++i) {
        if(a[i].w+tot>a[i].t) {
            if(a[i].w<q.top()) {
                tot-=q.top(),q.pop();
                tot+=a[i].w,q.push(a[i].w);
            }	
        } else tot+=a[i].w,q.push(a[i].w),++cnt;
    } printf("%d
",cnt);
}
}
signed main() {
    Luitaryi::main();
}

---

2019.07.22