当前位置： 移动技术网 > IT编程>开发语言>C/C++ > Emergency Evacuation(最短下车时间)———（思维）

Emergency Evacuation(最短下车时间)———（思维）

2020年04月12日  | 移动技术网IT编程  | 我要评论

格里芬十大扣篮高清,兵役证,江苏高速公路路况

题意：

给你一个车厢和一些人的位置，这些人都坐在座位上，求这些人全部出去的时间最小值。

注意：

有许多行座位，且每行关于过道对称，出口在过道一端，一个时间只能移动一个单位，且每时刻每个格子只能有一人

思路：

首先这道题不用算法。

然后有三个关键点：

  1. 每个人都有各不相同的唯一的一个出车时间。
  2. 最长出去的时间是最后一个人出去的时间。
  3. 要想最后一个人尽早出去，人们出去的顺序应与初始距离顺序相同。

解释一下第三条：

比如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("%d\n",dis[n]);
26     return 0;
27 }

 

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网