Emergency Evacuation(最短下车时间)———(思…
2020-04-11 16:00:51来源:博客园 阅读 ()
题意:
给你一个车厢和一些人的位置,这些人都坐在座位上,求这些人全部出去的时间最小值。
注意:
有许多行座位,且每行关于过道对称,出口在过道一端,一个时间只能移动一个单位,且每时刻每个格子只能有一人
思路:
首先这道题不用算法。
然后有三个关键点:
- 每个人都有各不相同的唯一的一个出车时间。
- 最长出去的时间是最后一个人出去的时间。
- 要想最后一个人尽早出去,人们出去的顺序应与初始距离顺序相同。
解释一下第三条:
比如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
原文链接:https://www.cnblogs.com/Lour688/p/12680273.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:捕获未经测试的返回值
- bzoj1003: [ZJOI2006]物流运输(最短路+DP) 2019-08-16
- 从存图到最短路算法的图论总结 2019-08-16
- 最短路 深搜 2019-04-12
- 最短点对 2019-01-01
- BZOJ1576: [Usaco2009 Jan]安全路经Travel(最短路 并查集) 2018-09-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash