打卡信奥刷题（2546）用C++实现信奥 P2107 小 Z 的 AK 计划-编程阁

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

说明/提示

对于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;}