13

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

 4 years ago
source link: http://www.cnblogs.com/Lour688/p/12680273.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

JzquIr7.png!web

a2yMBjF.png!web

faQnIvF.png!web

题意：

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

注意：

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

思路：

首先这道题不用算法。

然后有三个关键点：

  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 }

View Code

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK