csp信奥赛C++高频考点专项训练：【二分答案】案例6：Time 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 t=0 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…N+1: Line i+1 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
输入 1
4 3 5 8 14 5 20 1 16输出 1
2说明/提示
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代码
#include<bits/stdc++.h>usingnamespacestd;intn,ans=-1;// ans初始为-1，表示默认无解structwork{intt,e;// t为工作时间，e为截止时间}a[1010];// 按截止时间升序排序，贪心策略保证尽早处理截止时间早的任务boolcmp(work w1,work w2){returnw1.e<w2.e;}// 检查从时间x开始是否能完成所有工作boolcheck(intx){intnow=x;// 当前时间初始化为开始时间xfor(inti=1;i<=n;i++){// 处理第i个任务，若完成时间超过截止时间则失败if(now+a[i].t>a[i].e){returnfalse;}now+=a[i].t;// 更新当前时间}returntrue;// 所有任务均按时完成}intmain(){cin>>n;for(inti=1;i<=n;i++){cin>>a[i].t>>a[i].e;}// 按截止时间升序排序，确保处理顺序最优sort(a+1,a+n+1,cmp);// 二分查找最晚可行开始时间intl=0,r=a[n].e,mid;// r初始为最大截止时间while(l<=r){mid=(l+r)/2;if(check(mid)){// 当前mid可行，尝试更大的值ans=mid;l=mid+1;}else{// 不可行，减小右边界r=mid-1;}}cout<<ans;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++标准模板库STL：
https://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 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
