emu in blogjava
          
				
          
			          		
		
          
	
          

          

          
	
          
		
          
			
 
BlogJava ::
首頁(yè) ::
新隨筆 ::
聯(lián)系 ::
聚合
 ::
管理 ::


			
			
				

          
	
          
		
          
			
			
			
				 
				171 
				隨筆 ::
				103 文章
				::
				1052 評(píng)論
				::
				2 Trackbacks
			
		
          
	
          

          

			          		
		
          
	
          

          


          


          
	
					

          
	
	
	
          
		
          Problem Statement
          ????
          A group of vertical blocks are placed densely one after another on the ground. The blocks each have a width of 1, but their heights may vary. For example, if the heights of the vertical blocks are given as {1,5,5,1,6,1}, the configuration would look like the following picture:


          　　　　×
          　××　×
          　××　×
          　××　×
          　××　×
          ××××××
           
          Your task is to reproduce the exact shape of this structure using some number of non-intersecting rectangles. You will be given a int[] heights representing the heights of the vertical blocks from left to right. Return the minimal number of rectangles necessary to perform this task with the given configuration of blocks.
          Definition
          ????
          Class:
          BlockStructure
          Method:
          cover
          Parameters:
          int[]
          Returns:
          int
          Method signature:
          int cover(int[] heights)
          (be sure your method is public)
          ????
          

          Constraints
          -
          heights will have between 1 and 50 elements, inclusive.
          -
          Each element of heights will be between 1 and 1000, inclusive.
          Examples
          0)
          

          ????
          {1,5,5,1,6,1}
          Returns: 3
           
          We can use rectangles with sizes 6x1, 2x4 and 1x5.

          　　　　×
          　××　×
          　××　×
          　××　×
          　××　×
          ××××××

          1)
          

          ????
          {2,2,2,4,4}
          Returns: 2
           
          We can use a 3x2 rectangle and a 2x4 rectangle.


          　　　××
          　　　××
          ×××××
          ×××××


          2)
          

          ????
          {6,6,6,6,6,6}
          Returns: 1
          The structure is a rectangle.
          3)

          ××××××
          ××××××
          ××××××
          ××××××
          ××××××
          ××××××


          ????
          {71,44,95,16,10,80,12,17,98,61}
          Returns: 10
          It's impossible to use less than 10 rectangles.
          4)
          

          ????
          {100,100,97,100,100,100,97,98,99,99}
          Returns: 5
          

          This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
          
	
          
	
	
          
		posted on 2005-12-20 10:28 emu 閱讀(1987) 評(píng)論(3)  編輯  收藏  所屬分類: google編程大賽模擬題及入圍賽真題 
	
          

          







          
	    
    


          

          
	
          評(píng)論
          
		
		
				
          			
					
          
						# re: google中國(guó)編程挑戰(zhàn)賽入圍賽真題 -- BlockStructure(500分) 
							
								2005-12-21 14:06
							
						emu
					
          
					
          
						我覺(jué)得這組解是干擾數(shù)據(jù)：

          

          {2,2,2,4,4}

          Returns: 2

           

          We can use a 3x2 rectangle and a 2x4 rectangle.

          



          　　　××
          　　　××
          ×××××
          ×××××
          

          

          如果題目提供的解是這樣：

          



          　　　××
          　　　××
          ×××××
          ×××××
          

          

          答案就容易找的多了。  回復(fù)  更多評(píng)論
						
          
						  
					
          
				
          
				
          
			
				
          			
					
          
						# re: google中國(guó)編程挑戰(zhàn)賽入圍賽真題 -- BlockStructure(500分) 
							
								2006-06-28 15:43
							
						深藍(lán)色心情
					
          
					
          
						public static int count(int[] vs){

          		Arrays.sort(vs) ;

          		int min = vs[0] ;

          		

          		//把最低下一行刪掉。

          		List list = new LinkedList() ;

          		for(int i = 0 ; i < vs.length ; i++){

          			if(min != vs[i]){

          				int leftValue = vs[i] - min ;

          				if(leftValue > 0 ){

          					list.add(new Integer(leftValue)) ;

          				}

          			}

          		}

          		

          		int maxBox = 1 ;

          		

          		//分組

          		int step = 0 ;

          		int maxSize = list.size() ;

          		for(int i = 0 ; i < maxSize ; i++){

          			step = ((Integer)list.get(i)).intValue() ;

          			do{

          				if(i < maxSize){

          					int nextValue = -1000 ;

          					if(i + 1 < maxSize){

          						nextValue = ((Integer)list.get(i + 1)).intValue() ;

          					}

          					if(step == nextValue){

          						i++ ;

          					}else{

          						maxBox++ ;

          						break ;

          					}

          				}

          			}while(i < maxSize) ;

          		}

          		

          		return maxBox ;

          	}

          	

          

          	public static void main(String[] args) {

          		

          		int[] vs = {1,5,5,1,6,1} ;

          		

          		System.out.println(TestPlay.count(vs)) ;

          		

          		System.out.println(TestPlay.count(new int[]{6,6,6,6,6,6})) ;

          		

          		System.out.println(TestPlay.count(new int[]{2,2,2,4,4})) ;

          		

          		System.out.println(TestPlay.count(new int[]{71,44,95,16,10,80,12,17,98,61})) ;

          	}

          

          花了20分鐘才寫出來(lái).......，幸虧沒(méi)去比賽。

          不能輸入<0的數(shù)，大家看看這樣子寫是對(duì)的嗎？

            回復(fù)  更多評(píng)論
						
          
						  
					
          
				
          
				
          
			
				
          			
					
          
						# re: google中國(guó)編程挑戰(zhàn)賽入圍賽真題 -- BlockStructure(500分) 
							
								2008-06-20 21:31
							
						j
					
          
					
          
						看看我的是否更簡(jiǎn)單些:

          #include"stdio.h"

          int make(int *T,int p,int dem,int *n,int *min)

          {

          *min=10000;

          *n=0;

          for(int i=p;i<dem;i++)

          if(T[i]>0)

          {

          int s=i;

          while(T[s]>0&&s<dem)

          {

          if(T[s]<*min)

          *min=T[s];

          (*n)++;

          s++;

          }

          return i;

          }

          return dem;

          }

          void Sub(int *T,int s,int n,int min)

          {

          for(int i=0;i<n;i++)

          T[s+i]-=min;

          }

          int main(int argc, char* argv[])

          {    int p=0,n,m;

               int col[5]={3,3,6,6,6};

          	   while(true)

          		{

                  p=make(col,p,5,&n,&m);

          		if(p==5) 

                  break;

          	    printf("width:%d,height:%d\n",n,m);

          		Sub(col,p,n,m);

          		}

          	return 0;

          }

            回復(fù)  更多評(píng)論
						
          
						  
					
          
				
          
				
          
			

          




          








          

				

          




    







          
        
	




主站蜘蛛池模板：
井陉县|
福清市|
东安县|
濮阳市|
辰溪县|
苏尼特左旗|
来凤县|
鸡泽县|
佛冈县|
天祝|
青州市|
张掖市|
齐齐哈尔市|
特克斯县|
灵山县|
万山特区|
凤城市|
高淳县|
中牟县|
仁化县|
昭平县|
监利县|
揭阳市|
永顺县|
东源县|
清丰县|
嵊州市|
托克逊县|
敖汉旗|
白朗县|
三门峡市|
三明市|
石柱|
武宣县|
讷河市|
西吉县|
竹溪县|
海晏县|
依安县|
白玉县|
和田县|