P2107 小 Z 的 AK 计划
题目描述
在小 Z 的家乡，有机房一条街，街上有很多机房。每个机房里都有一万个人在切题。小 Z 刚刷完 CodeChef，准备出来逛逛。
机房一条街有nnn个机房，第iii个机房的坐标为xix_ixi，小 Z 的家坐标为000。小 Z 在街上移动的速度为111，即从x1x_1x1到x2x_2x2所耗费的时间为∣x1−x2∣|x_1 - x_2|∣x1−x2∣。
每个机房的学生数量不同，ACM 题目水平也良莠不齐。小 Z 到达第iii个机房后，可以花tit_iti的时间想题，然后瞬间 AK；当然，也可以过机房而不入。
小 Z 现在只有mmm个单位时间，之后他就该赶着去打 Codeforces 了。现在他想知道自己最多能在多少个机房 AK，希望你帮帮他。
输入格式
第一行包含两个整数n,mn,mn,m。
接下来nnn行，每行包含两个整数xi,tix_i,t_ixi,ti。
输出格式
第一行包含一个整数，表示小 Z 最多能 AK 的机房数量。
输入输出样例 #1
输入 #1
2 10 1 100 5 5输出 #1
1说明/提示
对于30%30\%30%的数据，n≤20n \leq 20n≤20。
对于60%60\%60%的数据，n≤1000n \leq 1000n≤1000。
对于100%100\%100%的数据，1≤n≤1051 \leq n \leq 10^51≤n≤105，0≤m,xi≤10180 \leq m,x_i \leq 10^{18}0≤m,xi≤1018，0≤ti≤1090 \leq t_i \leq 10^90≤ti≤109。
C++实现
//12252024832524#include<queue>#include<cstdio>#include<algorithm>#defineMax(x,y)(x>y?x:y)usingnamespacestd;typedeflonglongLL;constLL MAXN=100005;LL n,m;structnode{LL x,t;booloperator<(constnode&px)const{returnx<px.x;}}cr[MAXN];//computer room 机房priority_queue<LL>q;LLRead(){LL x=0,f=1;charc=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x*10)+(c^48);c=getchar();}returnx*f;}intmain(){n=Read();m=Read();for(inti=1;i<=n;++i){cr[i].x=Read();cr[i].t=Read();}sort(cr+1,cr+n+1);//按距离排序LL tim=0,ans=0,AK=0;for(inti=1;i<=n;++i){tim+=cr[i].x-cr[i-1].x;//走到i机房所用时间q.push(cr[i].t);//AK的欲望AK++;tim+=cr[i].t;while(!q.empty()&&tim>m){AK--;tim-=q.top();q.pop();}if(tim>m)//返还所有时间，但是仍然超过了mbreak;//别走了，再走也没时间AK了ans=Max(ans,AK);//取max}printf("%lld",ans);return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
)
)
