每日一题 5.26 建筑抢修

这是一个典型的贪心题（一看到题目我就发现早就写过了 复制粘贴就过了
我们首先排序一下截止时间从小到大 然后用一个大根堆存维修时间 用一个变量存总维修时间
当这个抢修这个新的房子发现时间不够时 弹出大根堆堆顶 如果减去这个时间加上当前时间小于之前的时间 就可以更新了 把抢修那个房子换成这个房子

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll const N=150010;
ll n,l,r,ans,tl;
priority_queue <ll,vector<ll>,less<ll>  >tt;
struct T{ll a,b;}t[N];
bool cmp(T x,T y){return x.b<y.b;}
int main()
{
   cin>>n;
   for(int i=1;i<=n;++i)cin>>t[i].a>>t[i].b;
   sort(t+1,t+1+n,cmp);
   tl=t[1].a,ans=1,tt.push(t[1].a);
   for(int i=2;i<=n;++i)
   {
       if(tl+t[i].a<t[i].b){ans++;tl+=t[i].a;tt.push(t[i].a);}
       else
       {
           l=tt.top();
           if(tl-l+t[i].a<tl)
           {
               tt.pop();
               tl=tl-l+t[i].a;
               tt.push(t[i].a);
           }
       }
   }
   cout<<ans<<endl;
  return 0;
}