Emergency Evacuation(最短下车时间)———（思维）
- 2020 年 4 月 11 日
- 筆記
题意：
给你一个车厢和一些人的位置，这些人都坐在座位上，求这些人全部出去的时间最小值。
注意：
有许多行座位，且每行关于过道对称，出口在过道一端，一个时间只能移动一个单位，且每时刻每个格子只能有一人
思路：
首先这道题不用算法。
然后有三个关键点：
- 每个人都有各不相同的唯一的一个出车时间。
- 最长出去的时间是最后一个人出去的时间。
- 要想最后一个人尽早出去，人们出去的顺序应与初始距离顺序相同。
解释一下第三条：
比如A和B，如果A的距离比B的距离大，那么B一定先到达门口，我们要让B先出。假设让A先出，那么B等A来的时候完全可以出去了，等A出去后再出去总时间就是time【A】+1。显然不如让B先出去，是time【A】。
方法：
我们将各个人的距离求出并排序，这就是人们的出车顺序，但是我们还要处理距离重复的，因为每个人都对应唯一的时间，挨个处理，若他与上一个人的距离相同，就让他等于上一个人的时间加一，后面同理，答案就是最后一个人的时间。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cmath> 4 #include <cstring> 5 #include <iostream> 6 using namespace std; 7 const int maxn=500*500*2+3; 8 int Exit,Road,n,dis[maxn]; 9 int main(){ 10 // freopen("1.in","r",stdin); 11 scanf("%d%d%d",&Exit,&Road,&n); 12 Road++;Exit++; 13 int x,y; 14 for(int i=1;i<=n;++i){ 15 scanf("%d%d",&x,&y); 16 if(y>=Road)y++; 17 dis[i]=(Exit-x)+abs(Road-y); 18 } 19 sort(dis+1,dis+1+n); 20 for(int i=2;i<=n;++i){ 21 if(dis[i]<=dis[i-1]){ 22 dis[i]=dis[i-1]+1; 23 } 24 } 25 printf("%dn",dis[n]); 26 return 0; 27 }
View Code
