自动搬运

查看原文

来自洛谷，原作者为

	PPL_ 一入信竞深似海，自闭只道是寻常

搬运于2025-08-24 21:34:04，当前版本为作者最后更新于2019-07-17 18:37:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题就一贪心

假设你有一种到了机房就必须AK的欲望

而且有超能力可以让自己AK的机房变得WA、TLE、MLE......，然后返还你的时间

假设你走到了一个机房，AK了之前的所有机房，但是时间超过了m，你是选择用时最少的机房WA掉，还是最多的呢(相当于路过)

答案肯定是不在用时最多的机房AK

于是按机房到家的距离从近到远排序

一个一个机房的去AK dreaming

当你当了i机房后，于是判断m时间是否用完，如果超了，那就反复使之前用最多时间AK的机房变得WA，并返还时间，直到用的时间少于m，那么继续往前走

在路上取max就好了

还没懂就看看代码实现

//12252024832524
#include <queue>
#include <cstdio>
#include <algorithm>
#define Max(x,y) (x>y?x:y)
using namespace std;

typedef long long LL;
const LL MAXN = 100005;
LL n,m;
struct node
{
	LL x,t;
	bool operator < (const node &px)const
	{
		return x < px.x;
	}
}cr[MAXN];//computer room 机房
priority_queue<LL> q;

LL Read()
{
	LL x = 0,f = 1;char c = getchar();
	while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
	while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
	return x * f;
}

int main()
{
	n = Read();
	m = Read();
	for(int i = 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(int i = 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)//如果用的时间多于m，发动超能力 
		{
			AK --;
			tim -= q.top();
			q.pop();
		}
		if(tim > m)//返还所有时间，但是仍然超过了m 
			break;//别走了，再走也没时间AK了
		ans = Max(ans,AK);//取max 
	}
	printf("%lld",ans);
	return 0;
}