久久久久亚洲国产AV麻豆,亚洲av成人一区二区三区,国产亚洲福利精品一区

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 閱讀(1985) 評論(3) 編輯收藏所屬分類: google編程大賽模擬題及入圍賽真題

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;
}
回復更多評論

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: 沒忍住手癢做了一道題，結果還沒作對。差點被燕潘考倒了 1000分模擬題CraneWork 500分模擬題 MaximalPalindromeSubstrings 250分模擬題 SalesRouting SecretSum (code jam china round2 500分真題) FactorialSystem (code jam china round2 300分真題) RecurringNumbers (code jam china 1000分真題) google中國編程挑戰賽入圍賽真題 -- HardDuplicateRemover(1000分) google中國編程挑戰賽入圍賽真題 -- BlockStructure(500分)

emu in blogjava

公告

常用鏈接

留言簿(92)

隨筆分類(20)

隨筆檔案(171)

文章分類(89)

文章檔案(103)

相冊

收藏夾(46)

友情連接

收藏

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

評論