Luogu P2107 小Z的AK计划

题目描述

https://www.luogu.com.cn/problem/P2107

简要题意：$x$ 轴上有 $n$ 个位置，第 $i$ 个位置的坐标为 $x_i$，初始时你位于 $0$，从 $x$ 走到 $y$ 需要花 $|x-y|$ 的时间，在第 $i$ 个位置，可以花 $t_i$ 的时间得到这个位置的收益（只能得到一次），每个位置的收益都是 $1$，现在你只有 $m$ 的时间，求最大收益

$n,m\le 10^5$

Solution

首先肯定不会向回走，那么我们枚举走到的最远的位置来计算答案即可，另外观察到收益全部相同，我们考虑反悔贪心

用大根堆维护所选的位置，如果不能到达第 $i$ 个位置，就依次从大根堆中 $pop$ 直到能够到达第 $i$ 个位置，然后如果我们能获得第 $i$ 个位置的收益，我们就直接获得并将其扔进大根堆中，否则就尝试替换花费时间最多位置

时间复杂度 $O(n\log n)$

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#define maxn 100010
#define ll long long
using namespace std;

int n; ll m; 

pair<ll, int> a[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; 
    for (int i = 1; i <= n; ++i) cin >> a[i].first >> a[i].second;
    sort(a + 1, a + n + 1); int ans = 0; 
    priority_queue<int> Q; 
    for (int i = 1; i <= n; ++i) {
        if (m < a[i].first) 
            while (!Q.empty()) m += Q.top(), Q.pop();
        if (m < a[i].first) break; 
        if (m >= a[i].first + a[i].second) m -= a[i].second, Q.push(a[i].second), ans = max(ans, (int) Q.size());
        else if (!Q.empty() && a[i].second < Q.top()) Q.pop(), Q.push(a[i].second); 
    } cout << ans << "\n"; 
    return 0;
}