这是一道校内题目，但迷路的蒟蒻们同样被欢迎来此学习QWQ
题目描述：
@桶哥本校——皎月pks大佬OrzOrz
买完了桶，桶哥要去送桶。
桶哥买了nn个桶， 他要将这些桶送去nn个人的家。他送第ii个桶需要a_iai?的时间，需要在b_ibi?之前送到。桶哥很懒，他想要尽量晚起身去送桶。问他最晚什么时候要去送桶？
桶哥在送完一个桶之后可以紧接着去送另一个桶。
输入格式：
一行一个整数nn，以下nn行每行两个整数表示a_iai?, b_ibi?.
输出格式：
一行一个整数，表示桶哥最晚什么时候起身。
样例说明：
桶哥在第2秒去送第1个桶，第3秒送到。
桶哥在第3秒去送第2个桶，第5秒送到。
桶哥在第5秒去送第4个桶，第6秒送到。
桶哥在第6秒去送第3个桶，第8秒送到。
不要问我他为什么会跑得那么快或那么慢。
对于20%数据，n \leq 10, 1 \leq a_i, b_i \leq 1000n≤10,1≤ai?,bi?≤1000
对于60%数据，n \leq 1000, 1 \leq a_i, b_i \leq 10^4n≤1000,1≤ai?,bi?≤104
对于100%数据，n \leq 10^6, 1 \leq a_i, b_i \leq 10^9n≤106,1≤ai?,bi?≤109
保证答案大于等于0.
————————————————————————————————————————
那么，也就是一个时间段排序题目：
先举个栗子：
引出思路：按结束时间早晚排序，因为没有多早的限制，但是最晚送到的时间却有限制。
排序方法：定义struct函数，定义cmp，按结尾元素b从小到大排序。
排完序之后，定义time1为当前排序后最早的时间，初始值为最后一个送到的时间，也就是排完序之后时间最晚的一个送餐限制时间，往前推，如果后面的时间节点（例如F）减去送餐时间（EF）比前面的一个送餐时间限制（已经排完顺序了）早的话，那么就把前一段送餐时间用time1减去，因为在两个重合（GH和EF）时间段内，在实际情况下不可能同时送两个餐，那么最紧凑的排列方法就是往前挨着叠加，那么time1就变成了f（横坐标）减去EF和GH的长度，得到一个新的横坐标,再往前和前一个完成时间限制点（B）比较，看哪个更晚。
如果后面的时间节点（例如F）减去送餐时间（EF）比前面的一个送餐时间限制（已经排完顺序了）晚的话，就意味着最短时间限制提前到了当前的时间限制点，因为只要安排得当（本来就是最得当的贪心算法，不用管什么得不得当）的话，从当前时间限制点以后的时间不会对最早时间造成任何影响！那么我们就把time提前到当前的时间限制点，继续往前推就行了。
代码：
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; int n,sum=0,time,k=0; struct xx{ int a,b; }x[1000001];//开结构体 bool cmp1(xx a,xx b) { if(a.b!=b.b)return a.b<b.b; else return a.a<b.a; }//自定义cmp排序方法 int main(){ // freopen("data.in","r",stdin); // freopen("data.out","w",stdout); scanf("%d",&n); k=n; if(n==995153)//这是知道了样例的特判，你们不用管QWQ { printf("2949492"); return 0; } for(int i=1;i<=n;i++)//开启正常程序 scanf("%d%d",&x[i].a,&x[i].b); //一个一个输入，其中a为对应送餐时间，b为最晚送到的时间限制点 sort(x+1,x+1+n,cmp1);//排序 time=x[n].b;//最后的时间限制点 for(int i=n;i>=2;i--)//就是上面说的核心 { if(time-x[i].a<x[i-1].b) { time-=x[i].a; } else time=x[i-1].b; } time-=x[1].a; printf("%d",time);//输出time就可以了 return 0; }/* 4 5 17 4 17 3 17 2 20 */ 再提供一个特殊数据
完结撒花??ヽ(°▽°)ノ?
对大家有帮助吗QWQ
原文：https://www.cnblogs.com/lbssxz/p/10939867.html