NC20154 [JSOI2007]建筑抢修(贪心)

题目链接

题意：



题解：

AC代码

/*
    Author:zzugzx
    Lang:C++
    Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

struct node{
    ll s,t;
}p[maxn];
bool cmp(node a,node b){
    return a.t<b.t;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>p[i].s>>p[i].t;
    sort(p+1,p+1+n,cmp);
    priority_queue<int>q;
    ll sum=0,ans=0;
    for(int i=1;i<=n;i++){
        if(sum+p[i].s<=p[i].t){
            ans++;sum+=p[i].s;
            q.push(p[i].s);
        }
        else if(q.top()>p[i].s){
            sum-=q.top();q.pop();
            sum+=p[i].s;q.push(p[i].s);
        }
    }
    cout<<ans<<endl;
    return 0;
}