Author: loop3r
Date: 20250916
tag: 反悔贪心
link: https://www.luogu.com.cn/problem/P2949

问题描述

link

分析

略

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
struct Node {
    int d, p;
} a[N];
int n;

bool cmp(const Node &a, const Node &b) {
    return a.d < b.d;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].d >> a[i].p;
    // 按照截止时间排序
    sort(a + 1, a + n + 1, cmp);

    long long ans = 0;
    priority_queue<int, vector<int>, greater<int>> q;

    for (int i = 1; i <= n; i++) {
        if (a[i].d == q.size()) {
            // 当前工作的截止时间等于队列中工作的数量（完成队列中工作花费的时间）
            if (a[i].p > q.top()) {
                ans -= q.top();
                q.pop();
                q.push(a[i].p);
                ans += a[i].p;
            }
        } else {
            q.push(a[i].p);
            ans += a[i].p;
        }
    }
    cout << ans << endl;

    return 0;
}