题解 | [JSOI2007]建筑抢修

#include <functional>
#include <iostream>
#include<bits/stdc++.h>
#include <queue>
#include <vector>
using namespace std;
using PII=pair<int,int>;
int main() {
    // int a, b;
    // while (cin >> a >> b) { // 注意 while 处理多个 case
    //     cout << a + b << endl;
    // }
    int n,time,ddl,currentTime=0,count=0;
    cin>>n;
    priority_queue<PII,vector<PII>,less<>> minHeap;
    vector<PII> v;
    for(int i=0;i<n;++i)
    {
        cin>>time>>ddl;
        // PII pii=make_pair(ddl-time,ddl);

        v.emplace_back(time,ddl);
        // minHeap.push(pii);
    }
    sort(v.begin(),v.end(),[](PII& a,PII& b){return a.second<b.second;});
    for(int i=0;i<n;++i)
    {
        // currentTime+=v[i].first;
        minHeap.push(v[i]);
        if(currentTime+v[i].first>v[i].second)
        {
            currentTime-=minHeap.top().first;
            minHeap.pop();
        }
        currentTime+=v[i].first;
        // if(!minHeap.empty())
        // {
        //     currentTime+=minHeap.top().first;
        //     // cout<<"pop "<<minHeap.top().first<<" "<<minHeap.top().second<<endl;
        //     count+=1;
        //     minHeap.pop();
        // }
    }
    cout<<minHeap.size()<<endl;
    return 0;

}
// 64 位输出请用 printf("%lld")

用大顶堆动态维护新任务加入后移除耗时最长的旧任务，使得执行相同个数任务时间最小，堆中剩余元素个数就是能按时完成的任务数