洛谷P2949 [USACO09OPEN]Work Scheduling G 题解

题目链接：P2949 [USACO09OPEN]Work Scheduling G

题意：

约翰有太多的工作要做。

为了让农场高效运转，他必须靠他的工作赚钱，每项工作花一个单位时间。

他的工作日从 \(0\) 时刻开始，有 \(10^9\) 个单位时间。

在任一时刻，他都可以选择编号 \(1\) 到 \(N\) 的 \(N(1 \leq N \leq 10^5)\) 项工作中的任意一项工作来完成。

因为他在每个单位时间里只能做一个工作，而每项工作又有一个截止日期，所以他很难有时间完成所有 \(N\) 个工作，虽然还是有可能。

对于第 \(i\) 个工作，有一个截止时间 \(D_i(1 \leq D_i \leq 10^9)\)，如果他可以完成这个工作，那么他可以获利 \(P_i( 1\leq P_i\leq 10^9 )\) 。

在给定的工作利润和截止时间下，约翰能够获得的利润最大为多少。

反悔型贪心经典题。

先把所有的工作按时间限制顺序排序。

然后我们从前往后扫一遍，遇到能做的工作就把它吃了

如果没法做，我们就把之前吃过的价值比它小的给吐出来。

这个过程等价于当时就选了这个工作，只不过当时还没遇到，先吃个垃圾占位。

我们可以用一个小根堆维护之前哪些工作可能成为垃圾。

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5+15))

int n,ans,d[N],p[N],o[N];
priority_queue< int,vector<int>,greater<int> > q;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++){ cin >> d[i] >> p[i]; o[i]=i; }
    sort(o+1, o+1+n, [](int a,int b) { return d[a] < d[b]; });
    for(int i=1; i<=n; i++)
    {
        int &P = p[o[i]], &D = d[o[i]];
        if(D > q.size())
        {
            q.push(P);
            ans += P;
        }else
        {
            if(q.top() < P)
            {
                ans += P - q.top();
                q.pop(); q.push(P);
            }
        }
    }
    cout << ans << '\n';
    return 0;
}