题意:
给你一个车厢和一些人的位置,这些人都坐在座位上,求这些人全部出去的时间最小值。
注意:
有许多行座位,且每行关于过道对称,出口在过道一端,一个时间只能移动一个单位,且每时刻每个格子只能有一人
思路:
首先这道题不用算法。
然后有三个关键点:
- 每个人都有各不相同的唯一的一个出车时间。
- 最长出去的时间是最后一个人出去的时间。
- 要想最后一个人尽早出去,人们出去的顺序应与初始距离顺序相同。
解释一下第三条:
比如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
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 以案例的形式,来分析用户思维、产品思维和工程思维
- 工程思维与产品思维
- Callback ——从同步思维切换到异步思维
- mybatis思维导图,让mybatis不再难懂(二) - java思维导图
- 百度发布智能城市“ACE王牌计划” 李彦宏要用AI思维吊打互联网思维
- 架构师思维
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
从Paxos到Zookeeper
倪超 / 电子工业出版社 / 2015-2-1 / 75.00元
《Paxos到Zookeeper:分布式一致性原理与实践》从分布式一致性的理论出发,向读者简要介绍几种典型的分布式一致性协议,以及解决分布式一致性问题的思路,其中重点讲解了Paxos和ZAB协议。同时,本书深入介绍了分布式一致性问题的工业解决方案——ZooKeeper,并着重向读者展示这一分布式协调框架的使用方法、内部实现及运维技巧,旨在帮助读者全面了解ZooKeeper,并更好地使用和运维Zoo......一起来看看 《从Paxos到Zookeeper》 这本书的介绍吧!