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

栏目: IT技术 · 发布时间: 4年前

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

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

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

题意:

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

注意:

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

思路:

首先这道题不用算法。

然后有三个关键点:

  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

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Java语言程序设计

Java语言程序设计

(美) Y. Daniel Liang / 李娜 / 机械工业出版社 / 2011-6 / 75.00元

本书是Java语言的经典教材,多年来畅销不衰。本书全面整合了Java 6的特性,采用“基础优先,问题驱动”的教学方式,循序渐进地介绍了程序设计基础、解决问题的方法、面向对象程序设计、图形用户界面设计、异常处理、I/O和递归等内容。此外,本书还全面且深入地覆盖了一些高级主题,包括算法和数据结构、多线程、网络、国际化、高级GUI等内容。 本书中文版由《Java语言程序设计:基础篇》和《Java语......一起来看看 《Java语言程序设计》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码