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 t1t→t1他将获得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 N1N1行第i 1 i1i1行包含两个用空格分隔的整数D i D_iDi​和P i P_iPi​输出格式只有一个数字表示 FJ 能够获得的最大利润。输入输出样例 1输入 13 2 10 1 5 1 7输出 117说明/提示在时间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 7101771017。思路分析题目大意有 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()说明当前工作更优。我们“反悔”掉之前那个利润最小的工作用当前的替换它。操作是从总利润中减去堆顶值弹出堆顶再将当前利润压入堆并累加。否则直接跳过当前这个利润更低的工作。通过这种“反悔”机制我们始终保证在时间允许的前提下堆里存的是截止到当前考虑过的工作中能获得的最大利润组合。代码实现#includebits/stdc.husingnamespacestd;// 定义工作结构体structW{intd;// 截止时间intp;// 利润}a[100010];// 按截止时间排序boolcmp(W x,W y){returnx.dy.d;}intmain(){intn;scanf(%d,n);for(inti1;in;i){scanf(%d%d,a[i].d,a[i].p);}// 第一步按截止时间排序sort(a1,an1,cmp);// 小根堆存已选工作的利润堆顶是最小利润priority_queueint,vectorint,greaterintq;longlongans0;// 总利润for(inti1;in;i){// 情况1时间还有空余直接选if(q.size()a[i].d){q.push(a[i].p);ansa[i].p;}// 情况2时间排满了考虑反悔替换elseif(!q.empty()a[i].pq.top()){ans-q.top();// 反悔掉利润最小的那个q.pop();q.push(a[i].p);ansa[i].p;}// 情况3其他情况利润更小或堆空直接忽略}printf(%lld\n,ans);return0;}功能分析数据结构结构体W存储每个工作的截止时间d和利润p。优先队列q是一个小根堆(priority_queueint, vectorint, greaterint)。它用来维护当前已选工作的利润堆顶始终是这些利润中的最小值便于我们找到那个最该被替换掉的“最差”选择。核心逻辑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)各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;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标准模板库STLhttps://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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}