洛谷P2107 小Z的AK计划 题解

题目链接：P2107 小Z的AK计划

题意：

在小 Z 的家乡，有机房一条街，街上有很多机房。每个机房里都有一万个人在切题。小 Z 刚刷完 CodeChef，准备出来逛逛。

机房一条街有 $n$ 个机房，第 $i$ 个机房的坐标为 $x_i$ ，小 Z 的家坐标为 $0$。小 Z 在街上移动的速度为 $1$，即从 $x_1$ 到 $x_2$ 所耗费的时间为 $|x_1 - x_2|$。

每个机房的学生数量不同，ACM 题目水平也良莠不齐。小 Z 到达第 $i$ 个机房后，可以花 $t_i$ 的时间想题，然后瞬间 AK；当然，也可以过机房而不入。

小 Z 现在只有 $m$ 个单位时间，之后他就该赶着去打 Codeforces 了。现在他想知道自己最多能在多少个机房 AK，希望你帮帮他。

输入格式：

第一行包含两个整数 $n,m$。

接下来 $n$ 行，每行包含两个整数 $x_i,t_i$。

输出格式：

第一行包含一个整数，表示小 Z 最多能 AK 的机房数量。

数据范围：

$1 \leq n \leq 10^5$，$0 \leq m,x_i \leq 10^{18}$，$0 \leq t_i \leq 10^9$。

考虑反悔贪心即可，每次直接选

发现时间不够选了，就把之前耗时最高的一个个扔掉。

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e5 + 15))

struct node { int x, t; } a[N];
priority_queue<int> q;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m; cin >> n >> m;
    rep(i, 1, n) cin >> a[i].x >> a[i].t;
    sort(a + 1, a + 1 + n, [&](node a, node b) { return a.x < b.x; });
    int tim = 0, res = 0, cnt = 0;
    rep(i, 1, n)
    {
        tim += a[i].x - a[i - 1].x;
        q.push(a[i].t); ++cnt; tim += a[i].t;
        while(!q.empty() && tim > m) { --cnt; tim -= q.top(); q.pop(); }
        if(tim > m) break; else up(res, cnt);
    }
    cout << res << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/0kd7zqe7