题解 P2107 【小Z的 AK 计划】
设二元组f[i]表示当前走到了第i个机房时，剩余多少时间，最多能ak多少题，STA表示选择ak的机房的集合（包括第i个），定义二元组运算，状态转移方程为：
表示如果时间本身就够，那么X可为空集，|x|=0，ak的题就加1，如果时间不够，那就需要在已选择ak的机房中去掉一部分来腾出时间，ak的题的数量就加上（1-去掉的机房数），在二元组运算过程中，剩余时间要保证>=0,最后答案为f[i]在i取1~n中的最大值，可是每次转移的代价太大，因此考虑优化。 由于每个机房都只能ak一次，所以考虑贪心，每次去掉耗时最大的机房，直到时间不超，这样可以用堆来维护选择ak的机房集合。 其实还可以从另外一个角度理解：
可以枚举最后ak的机房i，然后路程花费就是定值了，为x[i]，那剩下m-x[i]就能用于ak题目了，根据贪心，可以每次选择前i个机房中耗时最少的机房ak直到总时间超过m-x[i]，这个可以用堆来维护，这样每次的复杂度为O（nlogn），由于要枚举n个机房，总的时间复杂度为O（n^2logn)。可是光这样时间复杂度过高，无法忍受。考虑优化，实际上，枚举最后ak的机房时，从第i个到第i+1个时，前i+1个机房中耗时最少的并不需要重新统计，因为只是新增了第i+1个机房，所以目前的最小要么是前i个里的最小，要么就是第i+1个。
具体实现时，不必一个一个地添加，只需逆向思维，在考虑第i个机房为结束点时，只要在第i-1个机房为结束点的基础上先去掉耗时最大的直到时限不超。
因为每个机房只会进堆一次出堆一次，所以时间复杂度为O(nlogn）。
#include<iostream>
#include<algorithm>
#define f(i,l,r) for(i=(l);i<=(r);i++)
using namespace std;
const int MAXN=100005;
struct Bar{
long long x;
int t;
bool operator < (const Bar& X)const{
return x<X.x;
}
}a[MAXN];
int n,ans=0,sz;
long long m,sum,res;
long long heap[MAXN];
inline void pushup(int p) //堆的基本操作
{
int fa=p>>1,a=heap[p];
while(fa&&a>heap[fa]){
heap[p]=heap[fa];
p=fa;
fa>>=1;
}
heap[p]=a;
}
inline void pushdown(int p)
{
int son=p<<1,a=heap[p];
while(son<=sz){
if(son<sz&&heap[son+1]>heap[son]) son++;
if(a>=heap[son]) break;
heap[p]=heap[son];
p=son;
son<<=1;
}
heap[p]=a;
}
inline void insert(int a)
{
heap[++sz]=a;
pushup(sz);
}
inline void Pop()
{
heap[1]=heap[sz--];
pushdown(1);
}
int main()
{
ios::sync_with_stdio(false); //关闭流同步
int i,j;
cin>>n>>m;
f(i,1,n){
cin>>a[i].x>>a[i].t;
}
sort(a+1,a+1+n);
f(i,1,n){
res=m-a[i].x; //能分配给做题的时间
if(res<0) break;
sum+=a[i].t; //做题的总时间
insert(a[i].t); //将要做的题加入堆中
if(res-sum>=0){ //如果能分配的时间足够
ans=max(ans,sz);
}
else{
while(res-sum<0){ //根据贪心，每次把耗时最大的去掉，知道时间够
sum-=heap[1];
Pop();
}
ans=max(ans,sz); //更新答案
}
}
cout<<ans<<endl;
return 0;
}