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输入 11 2 13 1 -9 5 -3输出 11s说明/提示对于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_iTti​和收益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)代码实现#includebits/stdc.husingnamespacestd;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 longcpcn0;//清空计数器for(inti0;in;i){//读入n个任务intt,b;scanf(%d%d,t,b);if(b0)pos[cp]{t,b};//正收益存入pos数组elseneg[cn]{t,b};//负收益存入neg数组}//正收益任务按门槛t升序排序sort(pos,poscp,[](node x,node y){returnx.ty.t;});//负收益任务按(tb)降序排序贪心最优顺序sort(neg,negcn,[](node x,node y){returnx.tx.by.ty.b;});booloktrue;//标记是否可行//先处理所有正收益任务for(inti0;icp;i){if(Tpos[i].t){//当前时间不大于门槛无法完成okfalse;break;}Tpos[i].b;//完成正收益任务时间增加}if(!ok){//若正收益阶段已失败printf(-1s\n);//输出-1s并跳过负收益处理continue;}//再处理所有负收益任务for(inti0;icn;i){if(Tneg[i].t){//门槛不满足okfalse;break;}Tneg[i].b;//完成负收益任务时间减少if(T0){//完成之后时间必须大于0okfalse;break;}}//根据ok输出结果printf(ok?1s\n:-1s\n);}return0;}功能分析静态数组用全局pos[100005]和neg[100005]存储任务分别记录数量cp, cn避免使用vector。分组排序根据b的正负分别存入数组并按贪心策略排序。模拟执行先做所有正收益任务再做负收益任务。过程中任何门槛不满足或时间 ≤0 则失败。输出通过所有任务输出1s否则-1s。各种学习资料助力大家一站式学习和提升#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;}