题解 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;
}