castle_walls.java

一道很好的acm题目

import java.io.*;

public class castle_walls
{      DataInputStream input=new DataInputStream(System.in);
       int scenarios;
       int blue_number[]=new int[100];
	   int red_number[]=new int[100];
	   String buffer="";
	   int blue_or_red=0;
	   int stand_or_hook=0;
	   int stand_position;
	   int hook_position;
	   int UpStairs[]=new int[60001];
	   int DownStairs[]=new int[60001];
	   int result[]=new int[100];
	   
	              //0:none;
                  //1:Bule;
                  //2:Red;
                  //3:Red and Blue;
 


	   
	   
       public  void solve(int i) 
       {       
               int countX=0;
	           int UpPoint=1;//上指针
	           int DownPoint=1;//下指针
	           int countALL=0;//Blue线的计数器
           	   int countRP=0;//那个重要的计数器
	           while(countALL<blue_number[i])//把n条Blue线找完
		       {
		             while(UpStairs[UpPoint]%2!=1)//上墙不是Blue的话,不等于1和3，则为0或2
			         {   
			                if(UpStairs[UpPoint]==2)  { countRP++;}//如果是Red线
		                        	UpPoint++;
		             }
		
		             while(DownStairs[DownPoint]!=1)//下墙，等于0或3
			         { 
			                if(DownStairs[DownPoint]==2){ countRP--;}
			                         DownPoint++;
		             }
		             if(UpStairs[UpPoint]==3)//上墙交于一点
			         {
			                if(countRP<0)    {  countX++;}//负数，总数加1
			                         countRP++;
		             }
		             countX+=Math.abs(countRP);//总数加上cnt的绝对值
		             countALL++;
		             UpPoint++;
		             DownPoint++;
	           }
	           
	           result[i+1]=countX;
       }           

	   
       public static void main(String args[])
       {     
             castle_walls a=new castle_walls();
             a.read_input();
             for(int p=0;p<a.scenarios;p++)
             {
             	
             System.out.println("Scenario #" + (p+1) +":");
             System.out.println(a.result[p+1]);
             System.out.println("");
 
             }    
       }
       
       public   int  transform(String buffer,int blue_or_red)
       {        
                int index1,index2;
                index1=buffer.indexOf(' ');
                index2=buffer.lastIndexOf(' ');
                if(blue_or_red%2==0)
                return  Integer.parseInt(buffer.substring(0,index1));
                else 
                return  Integer.parseInt(buffer.substring(index2+1,buffer.length()));
                
       	       
       }
       public  void read_input()
       {     
             
             try
             { 
       	            scenarios=Integer.parseInt(input.readLine());
       	            for(int i=0;i<scenarios;i++)
       	            {     
       	                  buffer="";
       	                  blue_or_red=0;
       	                  if(i>=1)  //将上一步的结果清零
       	                  {
       	                         for(int n=1;n<blue_number[i-1]+red_number[i-1]+1;n++)
       	                         {
       	                                UpStairs[n]=0;
       	                                DownStairs[n]=0;
       	                         }
       	                  }
       	                  buffer=input.readLine();
       	                  blue_number[i]=transform(buffer,blue_or_red);
       	                  blue_or_red++;
       	                  red_number[i]=transform(buffer,blue_or_red);
       	                  blue_or_red++;
       	                  
       	                  for(int j=0;j<blue_number[i];j++)
       	                  {
       	                  	     buffer=input.readLine();
       	                  	     stand_position=transform(buffer,stand_or_hook);
       	                  	     stand_or_hook++;
       	                  	     hook_position=transform(buffer,stand_or_hook);
       	                  	     stand_or_hook++;
       	                  	     UpStairs[hook_position]=1;
       	                  	     DownStairs[stand_position]=1;
       	                  }
       	                  for(int k=0;k<red_number[i];k++)
       	                  {
       	                  	     buffer=input.readLine();
       	                  	     stand_position=transform(buffer,stand_or_hook);
       	                  	     stand_or_hook++;
       	                  	     hook_position=transform(buffer,stand_or_hook);
       	                  	     stand_or_hook++;
       	                  	     if(UpStairs[hook_position]==1)  
       	                  	          {UpStairs[hook_position]=3;
       	                  	           DownStairs[stand_position]=2;}
       	                  	     else 
       	                  	     {      
       	                  	           UpStairs[hook_position]=2;
		                               DownStairs[stand_position]=2;
                                 }
       	                  	     
       	                  }
       	                  solve(i);
       	                  
       	            }
       	            
       	     
       	     
       	     
       	     }catch(IOException e){System.out.println(e);}
       }
       
       
}