POJ 3505 Tower Parking - 追着光梦游

POJ 3505 Tower Parking

ACM解题报告 2017-08-12

Tower Parking

Description

There is a new revolution in the parking lot business: the parking tower. The concept is simple: you drive your car into the elevator at the entrance of the tower, and the elevator and conveyor belts drag the car to an empty parking spot, where the car remains until you pick it up. When you return, the elevator and conveyor belts move your car back to the entrance and you’re done.

The layout of the tower is simple. There is one central elevator that transports the cars between the different floors. On each floor there is one giant circular conveyor belt on which the cars stand. This belt can move in clockwise and counterclockwise direction. When the elevator arrives on a floor, it becomes part of the belt so that cars can move through it.

At the end of the day the tower is usually packed with cars and a lot of people come to pick them up. Customers are processed in a first come first serve order: the elevator is moved to the floor of the first car, the conveyor belt moves the car on the elevator, the elevator is moved down again, and so on. We like to know how long it takes before the last customer gets his car. Moving the elevator one floor up- or downwards takes 10 seconds and moving a conveyor belt one car in either direction takes 5 seconds.

Input

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

One line with two integers h and l with 1 ≤ h ≤ 50 and 2 ≤ l ≤ 50: the height of the parking tower and the length of the conveyor belts.

h lines with l integers: the initial placement of the cars. The jth number on the ith line describes the jth position on the ith floor. This number is −1 if the position is empty, and r if the position is occupied by the rth car to pick up. The positive numbers form a consecutive sequence from 1 to the number of cars. The entrance is on the first floor and the elevator (which is initially empty) is in the first position. There is at least one car in the parking tower.

Output

Per testcase:One line with the number of seconds before the last customer is served.
Sample Input
2
1 5
-1 2 1 -1 3
3 6
-1 5 6 -1 -1 3
-1 -1 7 -1 2 9
-1 10 4 1 8 -1
Sample Output
25
320
题目大意
题如果读不懂题意,就很难对数据进行处理!塔式停车场,每一层都可以停车,当顾客需要取车的时候,升降机就会升降到停车的 楼层,然后传输带就可以顺时针或者逆时针地进行转动,直到车的所在位置,然后升降机就降到出口处,完成取车的任务!不过过程需要注意升降机的升降位置就在上次的取车的位置开始。同时要注意到升降机需要走一个最短的路径,即需要判断到底是逆时针走还是顺时针走。
输入与输出

第一行一个正数:测试用例数,最多100个。
每个测试用例之后:一行有两个整数h和l,1≤h≤50,2≤l≤50;分别是停车塔的高度和输送带的长度。h行,每行l个数:汽车的初始位置。第i行上的第j个数字描述了第i个地板上的第j个位置。如果位置为空,则该数字为-1,如果位置被第r辆车占据,则为r。正数形成从1到车辆数量的连续序列。入口在一楼,电梯(最初是空的)处于初始位置。停车塔至少有一辆车。
输出的等到最后一位客户送达时的用时秒数。

#include <iostream>
#include<string.h>
using namespace std;

struct Node
{
    int x, y;
}pos[2501];//x,y分别表示第tmp个被取走的车的空间位置 

int turn[50];//是全局变量,未赋初值,元素全是0 
int main()
{
    int tcase, height, length;
     cin>>tcase;
    while(tcase--)
    {
         cin>>height>>length;
        int total = 0, tmp=0;
        for(int i = 0; i < height; i++)
            for(int j = 0; j < length; j++)
            {
                 cin>>tmp;
                if(tmp != -1)
                {
                     total++;//车在这一层总共的数量 
                     pos[tmp].x = j;
                     pos[tmp].y = i;
                }
            }
        //end of input
        int k = 1;
        int curX, curY, ans = 0;//cur=current 
        while(k <= total)
        {
            curY = pos[k].y;     
            curX = pos[k].x+turn[curY];
            if(curX >= length)
                 curX %= length;
            while(curX < 0)
                 curX += length;
            if(curX > length-curX)
            {
                 ans+=(length-curX)*5+curY*20;
                 turn[curY] += length-curX;
            }
            else
            {
                 ans += curX*5+curY*20;
                 turn[curY]-= curX;//turn[curY]用来判断离哪面近一点,节省时间 ,每一层用一个元素,减去当前位置 ,即可知道后来的位置 
            }
             k++;
            //cout<<"ans is "<<ans<<endl;
        }
         cout<<ans<<endl;
         memset(turn, 0, sizeof(turn));//memset常用于内存空间初始化 
     }
    return 0;
}

本文由 guopengli 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。
  • 浏览次数: 454
  • 还不快抢沙发

    添加新评论