Luogu P2949 [USACO09OPEN]Work Scheduling G

题目描述

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

简要题意：现在有 $n$ 个工作可以完成，完成每个工作需要 $1$ 的时间，完成第 $i$ 个工作可以获得 $c_i$ 的收益，第 $i$ 个工作的截止时间是 $d_i$，求最大获利

$n\le 10^5$

Solution

由于所有工作的完成时间相同，所以我们将所有工作按照截止时间排序，用小根堆维护已经选的工作，如果当前工作无法完成，就去替换一个收益最小的工作

时间复杂度 $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;

pair<int, int> a[maxn];

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

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].first >> a[i].second;
    sort(a + 1, a + n + 1); ll ans = 0;
    priority_queue<int, vector<int>, greater<int>> Q; 
    for (int i = 1; i <= n; ++i) {
        if (Q.size() < a[i].first) ans += a[i].second, Q.push(a[i].second);
        else if (Q.top() < a[i].second) ans += a[i].second - Q.top(), Q.pop(), Q.push(a[i].second); 
    } cout << ans << "\n"; 
    return 0;
}