Work Scheduling G（洛谷

Work Scheduling G（洛谷 - P2949 ）

[USACO09OPEN] Work Scheduling G（反悔贪心）

题面翻译

约翰有太多的工作要做。为了让农场高效运转，他必须靠他的工作赚钱，每项工作花一个单位时间。他的工作日从 $0$ 时刻开始，有 $10^9$ 个单位时间。在任一时刻，他都可以选择编号 $1$ 到 $N$ 的 $\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 )$ . 在给定的工作利润和截止时间下，约翰能够获得的利润最大为多少.

题目描述

Farmer John has so very many jobs to do! In order to run the farm efficiently, he must make money on the jobs he does, each one of which takes just one time unit.

His work day starts at time 0 and has 1,000,000,000 time units (!). He currently can choose from any of N (1 <= N <= 100,000) jobs

conveniently numbered 1…N for work to do. It is possible but

extremely unlikely that he has time for all N jobs since he can only work on one job during any time unit and the deadlines tend to fall so that he can not perform all the tasks.

Job i has deadline D_i (1 <= D_i <= 1,000,000,000). If he finishes job i by then, he makes a profit of P_i (1 <= P_i <= 1,000,000,000).

What is the maximum total profit that FJ can earn from a given list of jobs and deadlines? The answer might not fit into a 32-bit integer.

输入格式

* Line 1: A single integer: N

* Lines 2…N+1: Line i+1 contains two space-separated integers: D_i and P_i

输出格式

* Line 1: A single number on a line by itself that is the maximum possible profit FJ can earn.

样例 #1

样例输入 #1

样例输出 #1

提示

Complete job 3 (1,7) at time 1 and complete job 1 (2,10) at time 2 to maximize the earnings (7 + 10 -> 17).

题目大意：

约翰有很多工作要做，每个工作有一个截止时间和利润。他的工作日从时间 0 开始，且有非常多的时间单位（最多到 (10^9)）。每个工作占用一个时间单位。如果约翰能够在截止时间之前完成某项工作，他就能获得该项工作对应的利润。问题要求计算出他能通过合理安排工作的方式，获得的最大利润。

解题思路：

排序：
- 首先，可以将所有工作按截止时间 (D_i) 升序排序。因为如果工作安排不合理，可能会错过截止时间，排序后方便我们考虑如何在每个时间点选择最优工作。
使用优先队列：
- 为了使得在有限的时间内获取最大利润，我们可以使用一个优先队列（最小堆）。该堆中存储的是已选择工作的利润。
- 每次安排一个工作时，如果当前时间点能安排更多的工作，我们就将该工作加入队列。如果队列已满（即已经安排了足够的工作），并且当前工作的利润大于队列中的最小值，则替换队列中的最小值，确保队列内的工作都是利润较高的工作。
详细步骤：
- 将工作按截止时间排序，遍历每个工作，判断是否可以在截止时间之前完成。
- 如果能完成该工作并且时间尚余，就将该工作的利润加入堆中。否则，若队列已满且当前工作利润更高，则替换堆中最小的利润。
- 最后，堆中存储的即为约翰能够完成的所有工作，并且其总利润即为答案。

代码分析：

#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <bitset>
#include <iomanip>
#define endl '\n'
#define int long long
#define Max(a, b) (((a) > (b)) ? (a) : (b))
#define Min(a, b) (((a) < (b)) ? (a) : (b))
#define BoBoowen ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;const int inf = 1e9 + 7;
const int N = 2e5 + 10;
struct Node
{int tim; // 截止时间int mon; // 利润
} node[N];int cmp(struct Node &x, struct Node &y)
{return x.tim < y.tim;  // 按截止时间排序
}void solved()
{int n;cin >> n;for (int i = 0; i < n; ++i){cin >> node[i].tim >> node[i].mon;  // 输入截止时间和利润}sort(node, node + n, cmp);  // 按截止时间升序排序priority_queue<int, vector<int>, greater<int>> pq;  // 最小堆，用于存储当前选择的工作利润for (int i = 0; i < n; ++i){if (node[i].tim > pq.size())  // 如果可以再安排一个工作{pq.push(node[i].mon);  // 将当前工作的利润加入堆中}else  // 如果堆已满，比较当前工作利润是否能替换掉堆中最小的利润{if (node[i].mon > pq.top()){pq.pop();  // 弹出最小的pq.push(node[i].mon);  // 插入当前的工作}}}int ans = 0;while (!pq.empty())  // 最后计算总利润{ans += pq.top();pq.pop();}cout << ans;  // 输出最大利润
}signed main()
{BoBoowen;int T = 1; // 可以扩展到多组测试while (T--){solved();  // 调用解题函数}
}

解题分析：

排序：
- 首先按截止时间排序，确保我们优先考虑截止时间较早的工作。
优先队列（最小堆）：
- 优先队列用于存储当前选择的工作。通过最小堆的特性，我们可以在每次选择工作时快速替换掉利润最小的工作，以保证每次都选择最优的工作。
时间复杂度：
- 排序的时间复杂度为 (O(N \log N))。
- 使用优先队列的操作（插入和弹出）的时间复杂度为 (O(\log N))。
- 因此，总的时间复杂度为 (O(N \log N))，适合 (N \leq 10^5) 的规模。