题解 P2107 【小Z的AK计划】

思路:用 排序 + 堆 来实现贪心

不得不说这位小Z比我强太多了QAQ。


正片开始:

首先读入数据,处理一下从上一个机房走到本地点的路程(等会要用),然后按照当前地点到家的距离排序。

接下来就是求解部分:

首先,建立一个大根堆。然后遍历排好序的数据,要是这个房间能 AK ,那就 AK 了再走呗。要是这个机房时间不够了,就从原来那里找一个时间最大的,运用奥义·返还时间,把时间拿回来给这个机房AK。在这个过程中,要不断取(max)

在决策过程中,要是出现就算怎么反还时间也不够的话,说明后面的你压根就 AK 不了,所以明智的结束装B循环。

代码见下(图省事用了 pair ,因为可以不用重载运算符)。

#include<bits/stdc++.h>
#define int long long
#define pi pair<int,int>
#define F first
#define S second
#define mp make_pair
using namespace std;
pi a[100005];
priority_queue<pi> q;
int now,pro,sum;//now是当前时间,pro是当前题目,sum是最终答案
signed main() {
	int n,m;
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		int x,y;
		cin>>x>>y;
		a[i]=mp(x,y);
	}
	sort(a+1,a+n+1);
	for(int i=1; i<=n; i++) {
		now+=a[i].F-a[i-1].F;//加上走路的时间
		q.push(mp(a[i].S,a[i].F));
		++pro;
		now+=a[i].S;
		if(now>m) {
			while(now>m&&q.size()) {//返还时间
				pro--;
				now-=q.top().F;
				q.pop();
			}
		}
		if(now>m) {//上文所述明智选择
			break;
		}
		sum=max(sum,pro);
	}
	cout<<sum;
	return 0;
}
原文地址:https://www.cnblogs.com/ahawzlc/p/12599604.html