csp信奥赛C高频考点专项训练【二分答案】案例6Time Management S题目描述Ever the maturing businessman, Farmer John realizes that he must manage his time effectively. He has N jobs conveniently numbered 1…N (1 N 1,000) to accomplish (like milking the cows, cleaning the barn, mending the fences, and so on).To manage his time effectively, he has created a list of the jobs that must be finished. Job i requires a certain amount of time T_i (1 T_i 1,000) to complete and furthermore must be finished by time S_i (1 S_i 1,000,000). Farmer John starts his day at time t0 and can only work on one job at a time until it is finished.Even a maturing businessman likes to sleep late; help Farmer John determine the latest he can start working and still finish all the jobs on time.作为一名忙碌的商人约翰知道必须高效地安排他的时间。他有N ( 1 ≤ N ≤ 1000 ) N(1\le N\le 1000)N(1≤N≤1000)个工作要做比如给奶牛挤奶清洗牛棚修理栅栏之类的。为了高效约翰列出了所有工作的清单。第i ( 1 ≤ i ≤ N ) i(1\le i\le N)i(1≤i≤N)个工作需要T i ( 1 ≤ T i ≤ 1000 ) T_i(1\le T_i\le 1000)Ti​(1≤Ti​≤1000)单位的时间来完成而且必须在1 ≤ S i ≤ 10 6 1\le S_i\le 10^61≤Si​≤106或之前完成。现在是0 00时刻。约翰做一份工作必须直到做完才能停止。所有的商人都喜欢睡懒觉。请帮约翰计算他最迟什么时候开始工作可以让所有工作按时完成。如果始终无法完成全部任务输出− 1 -1−1输入格式* Line 1: A single integer: N* Lines 2…N1: Line i1 contains two space-separated integers: T_i and S_i输出格式* Line 1: The latest time Farmer John can start working or -1 if Farmer John cannot finish all the jobs on time.输入输出样例 1输入 14 3 5 8 14 5 20 1 16输出 12说明/提示Farmer John has 4 jobs to do, which take 3, 8, 5, and 1 units of time, respectively, and must be completed by time 5, 14, 20, and 16, respectively.Farmer John must start the first job at time 2. Then he can do the second, fourth, and third jobs in that order to finish on time.AC代码#includebits/stdc.husingnamespacestd;intn,ans-1;// ans初始为-1表示默认无解structwork{intt,e;// t为工作时间e为截止时间}a[1010];// 按截止时间升序排序贪心策略保证尽早处理截止时间早的任务boolcmp(work w1,work w2){returnw1.ew2.e;}// 检查从时间x开始是否能完成所有工作boolcheck(intx){intnowx;// 当前时间初始化为开始时间xfor(inti1;in;i){// 处理第i个任务若完成时间超过截止时间则失败if(nowa[i].ta[i].e){returnfalse;}nowa[i].t;// 更新当前时间}returntrue;// 所有任务均按时完成}intmain(){cinn;for(inti1;in;i){cina[i].ta[i].e;}// 按截止时间升序排序确保处理顺序最优sort(a1,an1,cmp);// 二分查找最晚可行开始时间intl0,ra[n].e,mid;// r初始为最大截止时间while(lr){mid(lr)/2;if(check(mid)){// 当前mid可行尝试更大的值ansmid;lmid1;}else{// 不可行减小右边界rmid-1;}}coutans;return0;}功能分析结构体与输入处理使用结构体work保存每个工作的耗时t和截止时间e。主函数中读取输入数据并存储到数组a中。排序策略按截止时间e升序排序确保优先处理截止时间更早的任务。这种贪心策略可以最大限度地避免因处理后续任务而错过早期截止时间。二分查找框架在可能的开始时间范围[0, 最晚截止时间]内进行二分查找寻找最大的可行开始时间。通过check函数验证中间值mid是否可行。验证函数check模拟从时间x开始按排序后的顺序处理所有任务依次累加时间并检查是否超出每个任务的截止时间。若全部任务通过检查则返回true否则返回false。时间复杂度排序复杂度为O(N log N)二分查找次数为O(log S)S为最大截止时间每次check需O(N)。总时间复杂度为O(N log N N log S)适用于题目数据范围。完整信奥赛C普及组CSP-J一等奖通关刷题题单及题解请关注专栏https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转【秘籍汇总】完整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信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C普及组csp-j初赛复赛真题题解持续更新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;}