Luogu - P4053 [JSOI2007]建筑抢修

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n;
struct build{
    int t1, t2;
}a[N];
int now, ans;
priority_queue<int> Q;

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

int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i].t1 >> a[i].t2;
    }
    
    sort(a + 1, a + n + 1, cmp);
    
    for(int i = 1; i <= n; i ++){
        if(a[i].t1 + now <= a[i].t2){
            now += a[i].t1;
            Q.push(a[i].t1);
            ans ++;
        }
        else{
            if(a[i].t1 < Q.top()){
                now -= Q.top();
                Q.pop();
                Q.push(a[i].t1);
                now += a[i].t1;
            }
        }
    }
    
    cout << ans;
    return 0;
}

上一篇:24 波特图和晶体管的混合Π模型


下一篇:【笔记】线性基