2003 ACM/ICPC Asia Regional Contest / Guangzhou
Zhongshan (Sun Yat-sen) University
Problem B
Elevator Stopping Plan
Input File: elevator.in
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 120 4 ) 1 31 ( = ´ - 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 410 10 29 4 30 = ´ + ´ 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
600 20 30 = ´ 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 12 4 3 = ´ second, then it will stop 10 seconds, then it will arrive 10th floor at
46 4 6 10 4 3 = ´ + + ´ 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 32 20 12 = + 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.
Input
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.
Output
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.
Sample Input
3 4 5 10
1 2
0
Output for the Sample Input
46
2 4 10
4
1 2
//-----------------------------------------------解答
根据题目意思，要尽量使最慢到达办公室的乘客的到达时间最短，假设电梯现在某1层，应该这样判断下一个乘客要求的层数应不应该停
t=从开始到现在已经花费的时间，初始值0
T=预计最后一名乘客到达他办公室的时间，初始值是最后一名乘客的层数*4(一层都不停的话)
假设现在电梯所在层次为 fc,下一个乘客的办公室所在层fi
如果乘客从现在所在层次爬楼梯到他办公室的到达时间 (fi-fc)*20+t
比在下一站停的话，最后一位乘客到他的办公室预计花费时间 T+10
要大的话，则在下一站停一下，以让下1位乘客的时间缩短，使最慢乘客的到达时间为比较小的 T+10 而不是比较大的 (fi-fc) *20+t
比如乘客要求停 4 5 10 层，电梯当前在1层
T=(10-1)*4=36
t=0
4层是否停？
如果不停，最慢乘客的时间大于或等于 (4-1)*20+t=60
如果停，最慢乘客的时间为等于 T=36
所以停,t=(4-1)*4+10=22,T=36+10=46
现在电梯来到4层， 5层是否停？
如果不停， 5层乘客现在下，最慢乘客的时间大于或等于 (5-4)*20+t=20+22=44
如果停,最慢乘客的时间为等于 T=46+10=56
所以不停
10层必须停
结果 时间=46，停止序列 4,10
//-------------C++程序实现
#include<fstream>
using namespace std;
int main(int argc, char* argv[])
{
const int iEleUpTime=4;
const int iManUpTime=20;
const int iElvStopTime=10;
fstream fin,fout;
fin.open(".\\in.txt",ios::in);
fout.open(".\\out.txt",ios::out);
fout.clear();
while(true)
{
int T=0; //----------------the last floor arrival time
int Sequance[31]; // ------the stoping sequance
int n=1; //----------------valid elements in Sequance
int Result[31]; //---------the result stoping sequance
int stops=0; //------------elevator stoping times
//---------------------input
fin>>n;
if(n==0)
break; //no more testcase ,quit
for(int i=0;i<n;i++)
{
fin>>Sequance[i];
}
//--------------------work
T=(Sequance[n-1]-1)*iEleUpTime;
int t=0; //-----------------------time passed
int iPreFloor=1;
for(int i=0;i<n;i++) //-----------loop for each required stoping floor
{
if(stops==0)
t=0;
else
{
t=Result[stops-1]* 4+10;
iPreFloor=Result[i-1];
}
if(t+(Sequance[i]-iPreFloor)*20>T+10)
{
Result[stops]=Sequance[i];
stops++;
T+=10;
}
}
T-=10; //-------------------------for the last floor stop
//---------------output
fout<<T<<endl;
fout<<stops<<" ";
for(int i=0;i<stops;i++)
{
fout<<Result[i]<<" ";
}
fout<<endl;
}
fin.close();
fout.close();
system("PAUSE");
return 0;
}
//----没答案，不知道对不对，大虾指点
