2003 ACM / ICPC Asia Regional Contest / Guangzhouzhongshan (Sun Yat-Sen) University
Problem Belevator Stopping Planinput File: Elevator.in
ZSoft Corp. is a software company in GaoKe Hall. And the workers in the hall are veryhard-working. But the elevator in that hall always drives them crazy. Why? Because there is onlyone elevator in GaoKe Hall, while there are hundreds of companies in it. Every morning, peoplemust 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 theelevator work more effectively. But it's not an easy job ... It takes 4 seconds for the elevator to ras 120 4) 1 31 (= '- seconds if the elevator goes from the 1st floor to the 31st flomwithout stop. And the elevator stops 10 second once. So, if the elevator stops at each floor, it willcost 410 10 29 4 30 = ' ' seconds (It is not necessary to calculate the stopping time at 31stfloor). In another way, it takes 20 seconds for the worker. It takes600 20 30 = 'seconds for them to walk from the 1st floor to the 31st floor. Obviously, it is not agood idea. So some people choose to use the elevator to get a floor which is the nearest to theiroffice. After thinking over for a long time, Hal finally found a . way to improve this situation He told theelevator man his idea: First, the elevator man asks the people which floors they want to go Hewill then design a stopping plan which minimize the time the last person need to arrive the floorwhere his office locates.. For example, if the elevator is required to stop at the 4th, 5th and 10th floor
'Second, Then IT Will Stop 10 Seconds, The IT Will Arrive 10th Floor AT46 4 6 10 4 3 =' 'Second. People Want To Go 4th Floor Will Reach Their Office At 12second, People Who Want To Go To 5th floor will reach at 32 20 12 = second and people whowant to go to 10th floor will reach at 46 second. Therefore it takes 46 seconds for the last person toreach 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 testcasesany more. f1 f2 ... fn area the floors at shich the elevator is to be stopped (n ≤ 30, 2 ≤ F1 Output For each testcase, output the time the last reading person needs in the first line and the stoppingfloors in the second line. Please note that there is a summary of the floors at the head of the secondline. There may be several solutions, any appropriate One IS Accepted. No Extra Spaces Are ALOWED. Sample INPUT3 4 5 101 20 Output for the Sample Input462 4 1041 2 //-----------------------------------------------answer According to the topic, try to make the shortest arrival time of the passengers in the office, assume that the elevator is now 1 layer, should determine the number of layers required by the next passenger should not stop T = From the beginning to the time that has been spent, the initial value is 0t = expects the last passenger to arrive at his office, the initial value is the last number of passengers * 4 (the first floor is not stopped) hypothesis now the elevator Level is FC, the next passenger's office Fi If the passenger climbed the stairs from now on the arrival time (Fi-Fc) * 20 t is stopped in the next stop, the last passenger arrived in his office. It is expected that T 10 is large, then stop in the next stop, so that the time of the next passenger is shortened, so that the slowest passenger arrives at the T 10 instead of relatively large (Fi-FC) ) * 20 t, such as passenger requirements stop 4 5 10, the elevator is currently at 1 layer T = (10-1) * 4 = 36 t = 04 layer stop? If you keep, the slowest passenger's time is greater than or equal to (4-1) * 20 t = 60 If stop, the slower passenger's time is equal to T = 36, stop, t = (4-1) * 4 10 = 22, t = 36 10 = 46 Now the elevator is coming to 4 layers, is the 5th floor stop? If you don't stop, the 5-layer passenger is now, the slowest passenger's time is greater than or equal to (5-4) * 20 t = 20 22 = 44 if stopped, the slowest passenger's time is equal to T = 46 10 = 56 So keep the 10 floors must stop the result time = 46, stop sequence 4, 10 // ------------- C program implementation #include INT main (int Argc, char * argv []) {const Ileuptime = 4; const IManuptime = 20; const 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 // -------------------- Work t = (sequance [n-1] -1) * ileuptime; int T = 0; // ----- ------------------ Time Passed Int iprefloor = 1; for (int i = 0; i // --------------- Output fout << t << endl; fout << stops << "; for (int i = 0; i } Fin.close (); fout.close (); system ("pause"); Return 0; } // ---- No answer, don't know right, prawn guidance
