[JSOI2007]建筑抢修

贪心

题面

$n$个建筑有维修时间$T_1$和开始不可维修时间点$T_2$，问最多能修多少建筑。

• $n\leq2*10^5$

解析

显然先按$T_2$排序维修，同时维护$-T_1$小根堆。
能修就加上$T_1$，否则如当前$T_1$小于堆顶就不修堆顶建筑转而修当前建筑。
能修就修，不能修就换。

然而我一开始弹堆顶的条件是弹完后可修当前建筑，缩小了弹的范围。。。
注意时刻向更优化。

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=2e5+100;
ll n,tot;
struct dat
{
  ll t,g;
  bool operator < (const dat &o) const {return -t>-o.t;}
}a[N];
priority_queue<dat>Q;
il bool cmp(dat x,dat y){return x.g<y.g;}
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
int main()
{
  n=gi();
  fp(i,1,n) a[i].t=gi(),a[i].g=gi();
  sort(a+1,a+1+n,cmp);
  fp(i,1,n)
    {
      if(tot+a[i].t<=a[i].g) Q.push(a[i]),tot+=a[i].t;
      else
    {
      re int gg=Q.top().t;
      if(gg>a[i].t) tot-=gg,Q.pop(),tot+=a[i].t,Q.push(a[i]);   
    }
    }
  printf("%lld\n",1ll*Q.size());
  return 0;
}