小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，希望你帮帮他。

对于 $100%$ 的数据，$1 \leq n \leq 10^5$，$0 \leq m,x_i \leq 10^{18}$，$0 \leq t_i \leq 10^9$。

分析

依题意模拟即可

首先对每个机房的 $x$ 进行一个排序。

显而易见， AK的个数与选择了那些机房无关。

注意到，每一个机房之间相互独立，可以贪心解决这个问题：

  • 按照距离逐个枚举机房。
  • 同时维护一个当前使用的时间，以及一个记录 $t$ 的大根堆。
  • 假设当前机房选择AK，判断时间是否超限。
  • 如果超限了，从大根堆中不断弹出机房，直到不超限；反之下一个机房。

对于每一个 $i$ ，都应当对 ans 进行一次更新。

注意数据范围（long long）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 5;

using pii = pair<int, int>;

int n, m, now, ans, res;

pii p[N];

priority_queue<int> q;

signed main(){
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> p[i].first >> p[i].second;
    }
    
    sort(p + 1, p + 1 + n);
    
    for (int i = 1; i <= n; i++){
        now += p[i].first - p[i - 1].first;
        now += p[i].second; ans++; q.push(p[i].second);
        while(q.size() && now > m){
            now -= q.top(); ans--; q.pop();
        }
        res = max(ans, res);
    }
    
    cout << res;
    
    return 0;
}

Written with StackEdit中文版.