题目描述

难度:[绿]普及+/提高

农夫约翰有很多工作要做！为了高效地经营农场，他必须从他所做的每一项工作中赚取利润，每项工作只需要一个时间单位。

他的工作日从时间$0$开始，总共有$10^9$个时间单位。他目前可以从$N(1 \leq N \leq 10^5)$项工作中选择要做的工作，这些工作被方便地编号为$1$到$N$。

虽然理论上他有可能完成所有$N$项工作，但实际上这是极不可能的，因为他在任何一个时间单位内只能完成一项工作，而截止日期通常会导致他无法完成所有任务。

第$i$项工作的截止时间为$D_i(1 \leq D_i \leq 10^9)$。如果他在截止时间前完成第$i$项工作，他将获得$P_i(1 \leq P_i \leq 10^9)$的利润。

给定一系列工作和截止日期，农夫约翰能够获得的最大总利润是多少？答案可能无法容纳在$32$位整数中。

输入样例

3 
2 10 
1 5 
1 7 

输出样例

17

算法

反悔贪心

$pre$是空闲的时间点，先将所有工作信息二元组$(D_i,P_i)$存在数组$works$中，将$works$按照$D_i$升序，$P_i$降序排列，然后按顺序安排每个工作。

对于工作$works[i]=(D_i,P_i)$，分为以下两种情况：

1. 如果$pre+1 \leq D_i$，说明这个工作可以直接安排，先将$P_i$累加到答案上，$pre$自增。
2. 否则当前工作不能直接安排，但是我们可以看看前面安排的哪一项工作是不如当前工作$(D_i,P_i)$的，选出最小的那一项反悔掉，转而安排$(D_i,P_i)$，$pre$保持不变。

因此在这个过程中准备一个用于反悔的小根堆，如果堆顶$\lt P_i$就反悔堆顶，把堆顶$heap.top()$弹出，让$P_i$入堆。答案更新为$ans=ans+P_i-heap.top()$。

复杂度分析

时间复杂度

对$works$排序的时间复杂度为$O(log_2n)$；按顺序安排每个工作需要遍历$O(n)$个工作，而每个工作在最差情况下有一个往堆中插入元素的操作，时间复杂度为$O(log_2n)$，所以安排$n$个工作的时间复杂度为$O(nlog_2n)$。整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

除了输入的$works$数组，整个算法的空间瓶颈在于反悔堆，在最差情况下堆中元素数量为$O(n)$，这也是整个算法的额外空间复杂度。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

int main() {
    int n;
    scanf("%d", &n);
    vector<vector<int>> works;
    for(int i = 0; i < n; i++) {
        int d, p;
        scanf("%d%d", &d, &p);
        works.push_back({d, p});
    }
    sort(works.begin(), works.end(), [&](auto&a, auto&b) {
        return a[0] != b[0]? a[0] < b[0]: a[1] > b[1];
    });
    priority_queue<int, vector<int>, greater<int>> heap;
    int pre = 0;
    LL ans = 0;
    for(int i = 0; i < n; i++) {
        if(pre + 1 <= works[i][0]) {
            ans += works[i][1];
            pre++;
            heap.push(works[i][1]);
        }else {
            if(!heap.empty() && heap.top() < works[i][1]) {
                ans += works[i][1] - heap.top();
                heap.pop();
                heap.push(works[i][1]);
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}