题意:有一个电梯在s层,电梯只能往下运行,经过一层的时间是1s,给出n个数据,表示第fi层的人在第ti秒到达,问最少多少时间可以把所有人带到第0层
思路:每个人单独算出到0层的时间,取最大的,再和s取最大值,就是答案,可以反证,若第k个人从他的楼层到第0层花的时间是最多的,如果在这个时间不能把所有人带到第0层,有2种情况,第一:在第k个人上面有人未进入电梯,因为每个人单独花费的时间为 ti+fi,第k层的时候电梯只需要在第tk时间到达即可,也就是上面有某些人到达的时间大于tk-(fk-fi),那么那些人单独到达的时间是大于 tk-fk+2fi 由于fk>fi 即时间 大于 tk+fi 且 tk+fi > tk+fl 结论与前提矛盾,故不成立,第二:第k个人下面在 tk+(fk-fi) 时间内未进入电梯,即有人单独话费的时间大于 tk+(fk-fi)+fi 即大于 tk+fk 显然也与前提矛盾,故,结论得证(mdzz,写个A题证个半天,感觉上来拍就是了,不要想那么多,wa了再说)
AC代码:
#include "iostream" #include "string.h" #include "stack" #include "queue" #include "string" #include "vector" #include "set" #include "map" #include "algorithm" #include "stdio.h" #include "math.h" #define ll long long #define bug(x) cout<<x<<" "<<"UUUUU"<<endl; #define mem(a) memset(a,0,sizeof(a)) using namespace std; const int N=1e5+100; int n,s,f,t,ans; int main(){ cin>>n>>s; for(int i=1; i<=n; ++i){ cin>>f>>t; int ti=t+f; ans=max(ans,ti); } cout<<max(ans,s); return 0; }