题意:
给你一个车厢和一些人的位置,这些人都坐在座位上,求这些人全部出去的时间最小值。
注意:
有许多行座位,且每行关于过道对称,出口在过道一端,一个时间只能移动一个单位,且每时刻每个格子只能有一人
思路:
首先这道题不用算法。
然后有三个关键点:
- 每个人都有各不相同的唯一的一个出车时间。
- 最长出去的时间是最后一个人出去的时间。
- 要想最后一个人尽早出去,人们出去的顺序应与初始距离顺序相同。
解释一下第三条:
比如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思维吊打互联网思维
- 架构师思维
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Java语言程序设计
(美) Y. Daniel Liang / 李娜 / 机械工业出版社 / 2011-6 / 75.00元
本书是Java语言的经典教材,多年来畅销不衰。本书全面整合了Java 6的特性,采用“基础优先,问题驱动”的教学方式,循序渐进地介绍了程序设计基础、解决问题的方法、面向对象程序设计、图形用户界面设计、异常处理、I/O和递归等内容。此外,本书还全面且深入地覆盖了一些高级主题,包括算法和数据结构、多线程、网络、国际化、高级GUI等内容。 本书中文版由《Java语言程序设计:基础篇》和《Java语......一起来看看 《Java语言程序设计》 这本书的介绍吧!