2 shunfurh shunfurh 于 2017.09.18 17:30 提问

Elevator Stopping Plan

Description

ZSoft Corp. is a software company in GaoKe Hall. And the workers in the hall are very hard-working. But the elevator in that hall always drives them crazy. Why? Because there is only one elevator in GaoKe Hall, while there are hundreds of companies in it. Every morning, people must waste a lot of time waiting for the elevator.Hal, a smart guy in ZSoft, wants to change this situation. He wants to find a way to make the elevator work more effectively. But its not an easy job.
There are H floors in GaoKe Hall. It takes 4 seconds for the elevator to raise one floor. It means:It costs (n-1)*4seconds if the elevator goes from the 1 st floor to the nth floor without stop. And the elevator stops 10 second once. So, if the elevator stops at each floor, it will cost (n-1)*4+(n-2)*10seconds (It is not necessary to calculate the stopping time at nth floor). In another way, it takes 20 seconds for the workers to go up or down one floor. It takes (n-1)*20seconds for them to walk from the 1 st floor to the nth floor. Obviously, it is not a good idea. So some people choose to use the elevator to get a floor which is the nearest to their office.
After thinking over for a long time, Hal finally found a way to improve this situation. He told the elevator man his idea: First, the elevator man asks the people which floors they want to go. He will then design a stopping plan which minimize the time the last person need to arrive the floor where his office locates. For example, if the elevator is required to stop at the 4 th , 5 th and 10 th floor, the stopping plan would be: the elevator stops at 4 th and 10 th floor. Because the elevator will arrive 4 th floor at 3*4=12second, then it will stop 10 seconds, then it will arrive 10 th floor at 3*4+10+6*4=46second. People who want to go 4 th floor will reach their office at 12
second, people who want to go to 5 th floor will reach at 12+20=32second and people who want to go to 10 th floor will reach at 46 second. Therefore it takes 46 seconds for the last person to reach his office. It is a good deal for all people.
Now, you are supposed to write a program to help the elevator man to design the stopping plan,which minimize the time the last person needs to arrive at his floor.
Input

The input consists of several test cases. Each test case is in a single line as the following:
n f1 f2 ... fn

It means, there are totally n floors at which the elevator need to stop, and n = 0 means no testcases
any more. f1 f2 ... fn are the floors at which the elevator is to be stopped (1<=n<=30000, 2<=f1< f2 ... fn<=30000). Every number is separated by a single space.
Output

For each testcase, output the time the last reading person needs in the a single line
Sample Input

3 4 5 10
1 2
0
Sample Output

46
4

1个回答

caozhy
caozhy   Ds   Rxr 2017.10.02 23:46
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
贪心算法之Elevator Stopping Plan
Elevator Stopping Plan Description ZSoft Corp. is asoftware company in GaoKe Hall. And the workers in the hall are veryhard-working. But the elevator in that hall always drives them crazy. Why?Becau
poj 1744 Elevator Stopping Plan
Elevator Stopping Plan Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 1896   Accepted: 631 Description ZSoft Corp. is a software company in GaoKe Hall. And th
[openjudge] 746:Elevator Stopping Plan
描述         Zsoft是一家在GaoKe大楼的软件公司,在这栋楼里所有工作人员都很勤奋。但是这栋楼里的电梯有毒。因为只有一个电梯,但是这栋楼里有上百个公司。每天早上,人们浪费了大量时间等电梯。Hal是ZSoft里的聪明人。想要改变这种状况。他想找一种可以有效利用电梯的方法,但这不容易。         在大楼里有H层,电梯4s上一层,也就是如果从一楼到n楼要花(n-1)*4s的时间。电
F - Elevator Stopping Plan
F - Elevator Stopping Plan题目意思:某个抠门的公司只有一个电梯, 现在有n 个人从1楼, 他们有各自想要到达的楼层, 然后电梯每上一楼需要4 s, 每在一个楼层开门需要10s, 然后然爬楼梯的话需要20s一楼。问, 如何用最短的时间让所有人都到达各自想要到的楼层。解题思路:本题解题思路为贪心算法+最小二分法。在本题中,花费时间最短为0,最长时间为在每层楼都停留一下的时间。...
pku1744 Elevator Stopping Plan
题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1744题意简述:n个人上不同的楼层,可以坐电梯,也可以走楼梯,其时间的花费题目已给的很明白了。求最后所有人完成上楼的后所花费时间的最小值。解题思路: 对于每个给定的时间t,我们可以使用贪心法确定是否可以在时间t内让所有人都到达目的层。显然,每一次电梯都尽量往上开。 比如说现在第i层有人要下
[openjudge] Elevator Stopping Plan
描述ZSoft Corp. is a software company in GaoKe Hall. And the workers in the hall are very hard-working. But the elevator in that hall always drives them crazy. Why? Because there is only one elevator in
UVALive - 2949 Elevator Stopping Plan
题意:有一个电梯,有n个人要上不同的目标层数,每个人可以选择搭电梯或走路,走路上一层或下一层都耗费20s,楼梯上一层要用4s,每次停下来持续10s, 最后一个目标层数的停靠时间不计。要求设计一个电梯停靠计划,使得最后一个人到达他的目标层数所用时间最小,输出这个最小时间。 思路:首先用二分查找时间,然后贪心这个时间是否满足所有的人,且尽量往高的地方去 #include #include #
POJ 1744 Elevator Stopping Plan
题意:N个人要到f1,f2...fn层楼,已知电梯每升一层要4秒,到某一层要停留10秒,人爬楼梯上一层要20秒。求出所有人都到达自己想去的楼层的最短时间。 分析:二分+贪心。对时间二分,贪心的判断在这固定的时间内是否能让所有人到达自己想去的楼层。贪心的判断就是让电梯尽可能的往上跑,以给要到较高楼层的人节省中间停留时间,而让时间比较充裕的到较低层的人尽可能多走楼梯,从而让总体时间最小。
Elevator Stopping Plan -UVALive - 2949
题意:某公司只有一个电梯, 现在有n 个人从1楼, 他们有各自想要到达的楼层, 然后电梯每上一楼需要4 秒, 每在一个楼层开门需要10 秒, 然后然爬楼梯的话需要20一楼。问, 如何用最短的时间让所有人都到达各自想要到的楼层。题解:满足条件的最小值,二分AC代码:#include &amp;lt;cstdio&amp;gt; #include &amp;lt;cstring&amp;gt; const int N = 32; ...
F - UVALive 2949 Elevator Stopping Plan
题意:公司只有一个电梯, 现在有n 个人从1楼, 他们有各自想要到达的楼层, 然后电梯每上一楼需要4 秒, 每在一个楼层开门需要10 秒, 然后然爬楼梯的话需要20一楼。问, 如何用最短的时间让所有人都到达各自想要到的楼层。题解思路:二分+贪心判断最短时间AC代码:#include &amp;lt;stdio.h&amp;gt;  #include &amp;lt;string.h&amp;gt;  const int N = ...