csp信奥赛C++高频考点专项训练之贪心算法 --【反悔贪心】：Work Scheduling G
csp信奥赛C++高频考点专项训练之贪心算法 --【反悔贪心】：Work Scheduling G
题目描述
农夫约翰有很多工作要做！为了高效地经营农场，他必须从他所做的每一项工作中赚取利润，每项工作只需要一个时间单位。
他的工作日从时间0 00开始，总共有10 9 10^9109个时间单位。他目前可以从N NN(1 ≤ N ≤ 10 5 1 \leq N \leq 10^51≤N≤105) 项工作中选择要做的工作，这些工作被方便地编号为1 11到N NN。
虽然理论上他有可能完成所有N NN项工作，但实际上这是极不可能的，因为他在任何一个时间单位内只能完成一项工作，而截止日期通常会导致他无法完成所有任务。
第i ii项工作的截止时间为D i D_iDi(1 ≤ D i ≤ 10 9 1 \leq D_i \leq 10^91≤Di≤109)。如果他在截止时间前完成第i ii项工作（如果当前时间为t tt，那么仅当D i > t D_i > tDi>t的时候他能做这个任务，完成后t → t + 1 t \rightarrow t+1t→t+1），他将获得P i P_iPi(1 ≤ P i ≤ 10 9 1 \leq P_i \leq 10^91≤Pi≤109) 的利润。
给定一系列工作和截止日期，FJ 能够获得的最大总利润是多少？答案可能无法容纳在32 3232位整数中。
输入格式
第一行输入一个整数N NN，意义见题目描述。
第二行到第N + 1 N+1N+1行：第i + 1 i+1i+1行包含两个用空格分隔的整数：D i D_iDi和P i P_iPi
输出格式
只有一个数字，表示 FJ 能够获得的最大利润。
输入输出样例 1
输入 1
3 2 10 1 5 1 7输出 1
17说明/提示
在时间1 11完成工作3 33( 1 , 7 ) \left(1,7\right)(1,7)，在时间2 22完成工作1 11( 2 , 10 ) \left(2,10\right)(2,10)以最大化收益，最后收益为7 + 10 = 17 7+10=177+10=17。
思路分析
题目大意：有 N 个工作，每个工作有一个截止时间D i D_iDi和利润P i P_iPi。单位时间只能做一个工作，问如何安排能获得最大利润。
核心思路：
这道题的贪心点在于，我们总是希望做利润更高的工作，但又不能超过截止时间。如果按照利润从大到小排序直接贪心，很可能会把时间浪费在利润高但耗时的工作上，导致来不及做其他利润虽低但耗时短的工作。
正确的反悔贪心策略如下：
- 按截止时间排序：先把所有工作按截止时间D i D_iDi从小到大排序。这样能保证我们先处理时间要求更紧迫的任务。
- 维护一个小根堆：我们用一个小根堆来维护当前已选工作的利润。堆顶是已选工作中利润最小的那个。
- 遍历与决策：
- 如果当前已选工作的数量
q.size()小于当前工作的截止时间a[i].d，说明我们还有时间做这个工作，直接将其利润a[i].p加入堆，并累加到总利润ans中。 - 如果当前已选工作的数量等于截止时间（说明时间已经排满了），我们就需要“反悔”了。
- 将当前工作的利润
a[i].p与堆顶（已选工作中利润最小者）比较。 - 如果
a[i].p > q.top()，说明当前工作更优。我们“反悔”掉之前那个利润最小的工作，用当前的替换它。操作是：从总利润中减去堆顶值，弹出堆顶，再将当前利润压入堆并累加。 - 否则，直接跳过当前这个利润更低的工作。
- 将当前工作的利润
- 如果当前已选工作的数量
通过这种“反悔”机制，我们始终保证在时间允许的前提下，堆里存的是截止到当前考虑过的工作中，能获得的最大利润组合。
代码实现
#include<bits/stdc++.h>usingnamespacestd;// 定义工作结构体structW{intd;// 截止时间intp;// 利润}a[100010];// 按截止时间排序boolcmp(W x,W y){returnx.d<y.d;}intmain(){intn;scanf("%d",&n);for(inti=1;i<=n;i++){scanf("%d%d",&a[i].d,&a[i].p);}// 第一步：按截止时间排序sort(a+1,a+n+1,cmp);// 小根堆：存已选工作的利润（堆顶是最小利润）priority_queue<int,vector<int>,greater<int>>q;longlongans=0;// 总利润for(inti=1;i<=n;i++){// 情况1：时间还有空余，直接选if(q.size()<a[i].d){q.push(a[i].p);ans+=a[i].p;}// 情况2：时间排满了，考虑反悔替换elseif(!q.empty()&&a[i].p>q.top()){ans-=q.top();// 反悔掉利润最小的那个q.pop();q.push(a[i].p);ans+=a[i].p;}// 情况3：其他情况（利润更小或堆空），直接忽略}printf("%lld\n",ans);return0;}功能分析
- 数据结构：
- 结构体
W存储每个工作的截止时间d和利润p。 - 优先队列
q是一个小根堆(priority_queue<int, vector<int>, greater<int>>)。它用来维护当前已选工作的利润，堆顶始终是这些利润中的最小值，便于我们找到那个最该被替换掉的“最差”选择。
- 结构体
- 核心逻辑：
if (q.size() < a[i].d)：这是一个关键的判断条件。因为单位时间只能做一个工作，q.size()代表了当前已经占用的时间长度。如果它小于当前工作的截止时间，意味着我们可以在不违反截止时间的情况下插入这个工作。- 反悔替换：当时间已满（
q.size() == a[i].d）时，若当前工作利润更高，我们就执行反悔操作。这保证了在已经排满的时间表里，我们总是保留着利润最高的那几个工作。
- 复杂度：
- 排序O ( n log n ) O(n \log n)O(nlogn)。
- 每个工作最多入堆、出堆一次，堆操作O ( log n ) O(\log n)O(logn)。
- 总时间复杂度 $O(n \log n) $ ，空间复杂度O ( n ) O(n)O(n)
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}【秘籍汇总】（完整csp信奥赛C++学习资料）：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
https://edu.csdn.net/course/detail/41081 点击跳转
3、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转
4、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转
5、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}