csp信奥赛C++高频考点专项训练之贪心算法 --【排序贪心】：魔法
csp信奥赛C++高频考点专项训练之贪心算法 --【排序贪心】：魔法
题目描述
cjwssb 知道是误会之后，跟你道了歉。你为了逗笑他，准备和他一起开始魔法。不过你的时间不多了，但是更惨的是你还需要完成n nn个魔法任务。假设你当前的时间为T TT，每个任务需要有一定的限制t i t_iti表示只有当你的T TT严格大于t i t_iti时你才能完成这个任务，完成任务并不需要消耗时间。当你完成第i ii个任务时，你的时间T TT会加上b i b_ibi，此时要保证T TT在任何时刻都大于0 00，那么请问你是否能完成这n nn个魔法任务，如果可以，输出+1s \texttt{+1}\texttt{s}+1s，如果不行，输出-1s \texttt{-1}\texttt{s}-1s。
输入格式
第一行：一个整数Z ZZ，表示有Z ZZ个测试点。
对于每个测试点：
第一行：两个整数n , T n,Tn,T，表示有n nn个任务,你一开始有T TT的时间。
接下来n nn行，每行2 22个数字，t i t_iti与b i b_ibi。
输出格式
对于每个测试点，输出+1s \texttt{+1}\texttt{s}+1s或者-1s \texttt{-1}\texttt{s}-1s。
输入输出样例 1
输入 1
1 2 13 1 -9 5 -3输出 1
+1s说明/提示
对于20 % 20\%20%的数据，n ≤ 10 n\leq10n≤10；
对于100 % 100\%100%的数据，n ≤ 10 5 , Z ≤ 10 , t i ≤ 10 5 , T ≤ 10 5 , − 10 5 ≤ b i ≤ 10 5 n\leq10^5,Z\leq10,t_i\leq10^5,T\leq10^5,-10^5\leq b_i\leq 10^5n≤105,Z≤10,ti≤105,T≤105,−105≤bi≤105。
思路分析
本题要求在初始时间 T 下，按一定顺序完成 n 个任务，每个任务有门槛t i t_iti（需T > t i T > t_iT>ti）和收益b i b_ibi（可为负）。完成所有任务后输出+1s，否则输出-1s。
关键贪心策略
将任务分为两组：
- b i ≥ 0 b_i \ge 0bi≥0的“正收益”任务
- b i < 0 b_i < 0bi<0的“负收益”任务
正收益任务：按t i t_iti升序处理。
因为门槛越低越容易满足，且完成后续时间增加，有利于后续任务。负收益任务：按t i + b i t_i + b_iti+bi降序处理。
推导：对于两个负收益任务 (i, j)，先做 i 再 j 的所需最小初始时间为max ( t i , t j − b i ) \max(t_i, t_j - b_i)max(ti,tj−bi)，先 j 后 i 为max ( t j , t i − b j ) \max(t_j, t_i - b_j)max(tj,ti−bj)。
若t i + b i > t j + b j t_i + b_i > t_j + b_jti+bi>tj+bj，则max ( t i , t j − b i ) ≤ max ( t j , t i − b j ) \max(t_i, t_j - b_i) \le \max(t_j, t_i - b_j)max(ti,tj−bi)≤max(tj,ti−bj)，即先 i 更优。
因此按t i + b i t_i + b_iti+bi从大到小排序。处理过程中时刻保证 (T > 0)，且在完成负收益任务后需重新检查 (T > 0)（因为b i < 0 b_i < 0bi<0可能使时间降至非正）。
复杂度
排序O ( n log n ) O(n \log n)O(nlogn)
代码实现
#include<bits/stdc++.h>usingnamespacestd;structnode{//任务结构体intt,b;//门槛t，收益b};intZ,n;//Z测试点个数，n任务数longlongT;//当前时间，用long long防止正收益累加溢出node pos[100005],neg[100005];//正收益任务数组，负收益任务数组intcp,cn;//正收益任务个数，负收益任务个数intmain(){scanf("%d",&Z);//读入测试点个数while(Z--){//循环每个测试点scanf("%d%lld",&n,&T);//读入n和初始时间T（注意%lld对应long long）cp=cn=0;//清空计数器for(inti=0;i<n;++i){//读入n个任务intt,b;scanf("%d%d",&t,&b);if(b>=0)pos[cp++]={t,b};//正收益存入pos数组elseneg[cn++]={t,b};//负收益存入neg数组}//正收益任务按门槛t升序排序sort(pos,pos+cp,[](node x,node y){returnx.t<y.t;});//负收益任务按(t+b)降序排序，贪心最优顺序sort(neg,neg+cn,[](node x,node y){returnx.t+x.b>y.t+y.b;});boolok=true;//标记是否可行//先处理所有正收益任务for(inti=0;i<cp;++i){if(T<=pos[i].t){//当前时间不大于门槛，无法完成ok=false;break;}T+=pos[i].b;//完成正收益任务，时间增加}if(!ok){//若正收益阶段已失败printf("-1s\n");//输出-1s并跳过负收益处理continue;}//再处理所有负收益任务for(inti=0;i<cn;++i){if(T<=neg[i].t){//门槛不满足ok=false;break;}T+=neg[i].b;//完成负收益任务，时间减少if(T<=0){//完成之后时间必须大于0ok=false;break;}}//根据ok输出结果printf(ok?"+1s\n":"-1s\n");}return0;}功能分析
- 静态数组：用全局
pos[100005]和neg[100005]存储任务，分别记录数量cp, cn，避免使用vector。 - 分组排序：根据
b的正负分别存入数组，并按贪心策略排序。 - 模拟执行：先做所有正收益任务，再做负收益任务。过程中任何门槛不满足或时间 ≤0 则失败。
- 输出：通过所有任务输出
+1s，否则-1s。
各种学习资料，助力大家一站式学习和提升！！！
#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;}