题解 P4053 【[JSOI2007]建筑抢修】

· · 题解

Solution

贪心加后悔堆操作 先把满足的丢进堆中 如果后面的可以优化就后悔操作一波 就可以得到最优解

#include<bits/stdc++.h>
using namespace std;
#define rg register
#define LL long long
const int maxN = 1e6+50;
inline int gi(){
    char ch=getchar();int x=0,q=0;
    while(ch<'0' || ch>'9') ch=='-'?q=1:0,ch=getchar();
    while(ch<='9' && ch>='0')x=x*10+ch-'0',ch=getchar();
    return q?(-x):x;
}
struct Plan{
    int tim,last;
}D[maxN];
priority_queue<int,vector<int>,less<int> > Q;
int n,now,Ans;
bool operator<(Plan A,Plan B){
    return A.last<B.last;
}
int main(){
    n=gi();
    for(int i=1;i<=n;i++){D[i].tim=gi();D[i].last=gi();}
    sort(D+1,D+n+1);
    for(int i=1;i<=n;i++){
        if(now+D[i].tim<=D[i].last){
            Ans++;
            Q.push(D[i].tim);
            now+=D[i].tim;
        }
        else{
            int u=Q.top();
            if(u>D[i].tim){
                Q.pop();
                Q.push(D[i].tim);
                now=now-u+D[i].tim;
            }
        }
    }

    cout<<Ans<<endl;
    return 0;

}