首页 > 专题系列 > Java解POJ > POJ 3505 Tower Parking [解题报告] Java
2013
11-12

POJ 3505 Tower Parking [解题报告] Java

Tower Parking

问题描述 :

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.

输入:

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.

输出:

Per testcase:

  • One line with the number of seconds before the last customer is served.

样例输入:

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

样例输出:

25
320

解题代码:

//* @author: 
import java.util.Scanner;
import java.util.Arrays;
public class Main{
  public static void main(String args[]){
    Scanner sc=new Scanner(System.in);
	int nn,n,m,ans;
     nn=sc.nextInt();
     while((nn--)!=0) {
      n=sc.nextInt();
      m=sc.nextInt();
      int a[][]=new int[n+1][m+1];
       ans=0;
	for (int i=1;i<=n;i++) {
	  for (int j=1;j<=m;j++) 
           a[i][j]=sc.nextInt();
	    int tp=0,now=1,t1,t2;
	    for (int j=1;j<=m;j++) if (a[i][j]!=-1) tp++;
		 while ((tp--)!=0) {
		  int pos=1,tmp=1000000;
		 for (int j=1;j<=m;j++) if (a[i][j]!=-1&&a[i][j]< tmp) {pos=j;tmp=a[i][j];}
		  ans+=(i-1)*20;
		t1=now-pos;
		t2=pos-now;
		if (t1< 1) t1+=m;
		if (t2< 1) t2+=m;
		if (t1>t2) t1=t2;
		ans+=t1*5;now=pos;
		a[i][pos]=-1;
	}
     }
     System.out.printf("%d\n",ans);
	}
  }
}

  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  2. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  3. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }