当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

1771:Elevator Stopping Plan

Special Judge 特殊评判
题目描述
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 it’s not an easy job.
There are 31 floors in GaoKe Hall. It takes 4 seconds for the elevator to raise one floor. It means:
It costs (31-1)*4=120 seconds if the elevator goes from the 1st floor to the 31st floor without stop. And the elevator stops 10 second once. So, if the elevator stops at each floor, it will cost 30*4+29*10 = 410 seconds (It is not necessary to calculate the stopping time at 31st floor). In another way, it takes 20 seconds for the workers to go up or down one floor. It takes 30*20 = 600 seconds for them to walk from the 1st floor to the 31st 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 4th, 5th and 10th floor,the stopping plan would be: the elevator stops at 4th and 10th floor. Because the elevator will arrive 4th floor at 3*4 = 12 second, then it will stop 10 seconds, then it will arrive 10th floor at 3*4+10+6*4 = 46 second. People who want to go 4th floor will reach their office at 12 second, people who want to go to 5th floor will reach at 12+20 = 32 second and people who want to go to 10th 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.
输入解释
The input consists of several testcases. Each testcase 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 (n <= 30, 2 <= f1 < f2 ... fn <= 31). Every number is separated by a single space.
输出解释
For each testcase, output the time the last reading person needs in the first line and the stopping floors in the second line. Please note that there is a summary of the floors at the head of the second line. There may be several solutions, any appropriate one is accepted. No extra spaces are allowed.
输入样例
3 4 5 10
1 2
0
输出样例
46
2 4 10
4
1 2

该题目是Virtual Judge题目,来自 北京大学POJ

题目来源 Asia Guangzhou 2003

源链接: POJ-1771

最后修改于 2020-10-29T06:13:40+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
1000 30000