csp信奥赛C++高频考点专项训练之贪心算法 --【反悔贪心】：建筑抢修
csp信奥赛C++高频考点专项训练之贪心算法 --【反悔贪心】：建筑抢修
题目描述
小刚在玩 JSOI 提供的一个称之为“建筑抢修”的电脑游戏：经过了一场激烈的战斗，T 部落消灭了所有 Z 部落的入侵者。但是 T 部落的基地里已经有N NN个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全毁坏。现在的情况是：T 部落基地里只有一个修理工人，虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序，以抢修尽可能多的建筑。
输入格式
第一行，一个整数N NN。
接下来N NN行，每行两个整数T 1 , T 2 T_1,T_2T1,T2描述一个建筑：修理这个建筑需要T 1 T_1T1秒，如果在T 2 T_2T2秒之内还没有修理完成，这个建筑就报废了。
输出格式
输出一个整数S SS，表示最多可以抢修S SS个建筑。
输入输出样例 1
输入 1
4 100 200 200 1300 1000 1250 2000 3200输出 1
3说明/提示
对于100 % 100 \%100%的数据，1 ≤ N < 150000 1 \le N < 1500001≤N<150000，1 ≤ T 1 < T 2 < 2 31 1 \le T_1 < T_2 < 2^{31}1≤T1<T2<231。
思路分析
1. 题目理解
我们有：
N个建筑，每个建筑有两个参数：T1：修复时间（必须连续占用修理工人）T2：截止时间（必须在T2之前完成修复）
- 工人一次只能修一个建筑
- 修复从 0 时刻开始，按某种顺序修复
- 目标是修尽可能多的建筑
2. 为什么简单贪心不行？
容易想到的两种贪心策略：
按截止时间
T2升序排序- 这符合“尽早完成截止早的任务”的想法
- 但可能因为某个任务耗时很长，导致后面的任务虽然截止晚但也被耽误
按修复时间
T1升序排序- 先修耗时短的，可以在有限时间内多完成几个
- 但可能错过一个截止时间早但耗时稍长的任务，导致总数量更少
3. 简单贪心反例
反例一：按截止时间 T2升序排序的贪心
| 建筑 | 修复时间 T1 | 截止时间 T2 |
|---|---|---|
| 1 | 100 | 101 |
| 2 | 1 | 102 |
| 3 | 1 | 102 |
| … | … | … |
| 101 | 1 | 102 |
共 101 个建筑：1 个耗时 100、截止 101 的建筑，和 100 个耗时 1、截止 102 的建筑。
贪心过程（按 T2升序）：
按 T2升序，建筑 1 最先。修复建筑 1 花费 100 秒，当前时间 = 100。
接着依次尝试修复建筑 2~101：
- 修复建筑 2：时间 = 101 ≤ 102 ✓，当前时间 = 101
- 修复建筑 3：时间 = 102 ≤ 102 ✓，当前时间 = 102
- 修复建筑 4：时间 = 103 > 102 ✗，无法修复
最终只能修复建筑 1、2、3，共3个。
最优解：
放弃建筑 1，只修复 100 个耗时 1 的建筑。总耗时 = 100 ≤ 102，共修复100个。
贪心结果远小于最优解。
反例二：按修复时间 T1 升序排序的贪心
| 建筑 | T1 | T2 |
|---|---|---|
| 1 | 2 | 2 |
| 2 | 2 | 2 |
| 3 | 1 | 100 |
贪心过程（按 T1升序）：
排序后顺序为：建筑 3（1,100）、建筑 1（2,2）、建筑 2（2,2）
- 修建筑 3：耗时 1，当前时间 = 1
- 尝试修建筑 1：需要时间 2，结束时间 = 3 > 2 ✗
- 尝试修建筑 2：同样 3 > 2 ✗
结果只能修 1 个建筑。
最优解：
先修建筑 1（2,2）：结束时间 2
再修建筑 3（1,100）：结束时间 3 ≤ 100
共修2个建筑（建筑 1 和 3）。
贪心结果（1 个）小于最优解（2 个）。
4. 简单贪心思路总结
上面的两个反例清楚地说明了：
- 单纯按截止时间贪心，可能被一个耗时很长的早期任务拖累，导致后面大量短任务无法完成。
- 单纯按修复时间贪心，可能因为优先修了一个耗时短但截止很晚的任务，错过了两个耗时稍长但截止极早的任务。
这也是为什么需要“反悔贪心”——在按截止时间排序的基础上，用最大堆维护已选任务的耗时，当新任务无法加入时，用更短的任务替换掉已选中最耗时的任务，从而在保证截止时间的前提下最大化数量。
反悔贪心思路
思路：
- 排序：按截止时间T 2 T_2T2从小到大排序。这样可以保证我们优先考虑那些时间紧迫的建筑。
- 贪心选择：遍历每个建筑，若当前已用总时间 now加上当前建筑的修理时间t 1 t_1t1不超过其截止时间t 2 t_2t2，则直接选择修理，将t 1 t_1t1加入最大堆（记录已选建筑的修理时间），并更新n o w nownow。
- 反悔操作：若当前建筑无法直接加入（即n o w + t 1 > t 2 now + t_1 > t_2now+t1>t2），但堆非空且堆顶（已选建筑中修理时间最长的）大于当前建筑的t 1 t_1t1，则用当前建筑替换掉那个耗时最长的建筑。这样操作后，now 减小（减去原最长耗时，加上当前t 1 t_1t1），总时间更优，且修理数量不变。这相当于反悔了之前的一个选择，为后续可能更优的建筑腾出时间。
- 结果：最终堆的大小即为最多能修理的建筑数量。
正确性：
通过反悔操作，我们始终维护一个在已考虑的建筑中，在保证数量最多的前提下，总耗时最小的方案。由于是按截止时间顺序处理，且每次反悔都使总耗时减小，因此最终得到最优解。
代码实现
#include<bits/stdc++.h>usingnamespacestd;// 建筑结构体structB{intt1;// 修理耗时intt2;// 截止时间}a[150005];// 按截止时间排序boolcmp(B x,B y){returnx.t2<y.t2;}intmain(){intn;scanf("%d",&n);for(inti=1;i<=n;i++){scanf("%d%d",&a[i].t1,&a[i].t2);}sort(a+1,a+n+1,cmp);// 按截止时间升序priority_queue<int>q;// 大根堆，存放已选建筑的修理时间longlongnow=0;// 当前已用总时间for(inti=1;i<=n;i++){// 如果能直接修当前建筑if(now+a[i].t1<=a[i].t2){now+=a[i].t1;q.push(a[i].t1);}// 不能直接修，考虑反悔：用当前建筑替换一个耗时最长的已修建筑elseif(!q.empty()&&q.top()>a[i].t1){now=now-q.top()+a[i].t1;// 替换后总时间变化q.pop();q.push(a[i].t1);}}printf("%d\n",q.size());// 堆的大小即为最多建筑数return0;}功能分析
- 结构体
B：存储每个建筑的修理时间t1和截止时间t2。 - 排序
cmp：按截止时间升序排列，确保先考虑时间要求紧的建筑。 - 大根堆
q：维护已选建筑的修理时间，堆顶是当前已选建筑中耗时最长的。 - 变量
now：记录当前已选建筑的总修理时间。 - 主循环：
- 情况1：若当前建筑可以直接加入（总时间不超过截止时间），则直接加入，更新
now和堆。 - 情况2：若不能直接加入，但堆顶耗时大于当前建筑耗时，说明用当前建筑替换堆顶建筑可以使总时间减少，且数量不变，故执行反悔操作：减去原堆顶时间，加上当前时间，更新堆。
- 情况1：若当前建筑可以直接加入（总时间不超过截止时间），则直接加入，更新
- 输出：堆的大小即为能修理的最大建筑数。
各种学习资料，助力大家一站式学习和提升！！！
#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;}