emu in blogjava
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  171 随笔 :: 103 文章 :: 1052 评论 :: 2 Trackbacks
google中国编程挑战赛入围赛真题 -- BlockStructure(500分)

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 阅读(1940) 评论(3)  编辑  收藏 所属分类: google编程大赛模拟题及入围赛真题

评论

# re: google中国编程挑战赛入围赛真题 -- BlockStructure(500分) 2005-12-21 14:06 emu
我觉得这组解是干扰数据：

{2,2,2,4,4}
Returns: 2

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



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

如果题目提供的解是这样：



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

答案就容易找的多了。  回复  更多评论
  

# re: google中国编程挑战赛入围赛真题 -- BlockStructure(500分) 2006-06-28 15:43 深蓝色心情
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分钟才写出来.......，幸亏没去比赛。
不能输入<0的数，大家看看这样子写是对的吗？
  回复  更多评论
  

# re: google中国编程挑战赛入围赛真题 -- BlockStructure(500分) 2008-06-20 21:31 j
看看我的是否更简单些:
#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;
}
  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: