【堆】小X的AK计划
思路
先按位置排序
然后一个一个加,如果超过就去掉之前用最多的时间的机房
注:
这里用到了大根堆
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define ll long long
using namespace std;
ll Sum,Num,Ans,n,m,x,y,t;
struct AK
{
ll Place,Time;
}F[100250];
bool Cmp(AK i,AK j)
{return i.Place<j.Place;}//按位置排
int main()
{
// freopen("1.in","r",stdin);
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=n;++i)
{
scanf("%lld%lld",&x,&y);
if(x+y>m)continue;//优化//如果两个加起来超过m
F[++t].Place=x;
F[t].Time=y;
}
sort(F+1,F+t+1,Cmp);
priority_queue<int>K;//大根堆
for(ll i=1;i<=t;++i)
{
K.push(F[i].Time);
Sum+=F[i].Time+(F[i].Place-F[i-1].Place);//时间
Num++;//AK的机房
if(Sum>m)//如果超时
{
Sum-=K.top();//去掉堆顶,也就是之前AK所用的时间最长的机房
K.pop();
Num--;
}
Ans=max(Ans,Num);//去最大的
}
printf("%lld",Ans);
return 0;
}