Topcoder上的一道題目，題目描述如下：

Problem Statement

Byteland is a city with many skyscrapers, so it's a perfect venue for BASE jumping. Danilo is an enthusiastic BASE jumper. He plans to come to Byteland and to jump off some of its buildings.

Danilo wants to make M jumps in Byteland. However, he has some rules. First, he never jumps off the same building twice. Second, all buildings he selects for his jumps must have the same number of floors. (This is for safety reasons: It is hard to get the timing right if each jump starts at a different height.)

Philipe is the mayor of Byteland. He welcomes Danilo's visit as he would like to use it as a publicity stunt. However, Philipe knows that Danilo will only come to Byteland if there are at least M buildings that each have the same number of floors. To ensure that, the mayor is willing to build additional floors on some of the skyscrapers in Byteland.

You are given the int M and a int[] heights. Each element of heights is the number of floors in one of Byteland's skyscrapers. Compute and return the smallest number of additional floors the mayor has to build so that there will be at least M buildings with the same number of floors.

Definition

Class:

BuildingHeightsEasy

Method:

minimum

Parameters:

int, int[]

Returns:

int

Method signature:

int minimum(int M, int[] heights)

(be sure your method is public)

Limits

Time limit (s):

2.000

Memory limit (MB):

256

Constraints

-

heights will contain between 1 and 50 elements, inclusive.

-

M will be between 1 and the number of elements in heights, inclusive.

-

Each element in heights will be between 1 and 50, inclusive.

Examples

0)

2

{1, 2, 1, 4, 3}

Returns: 0

Note that we already have two buildings that have the same number of floors. Hence, no additional floors need to be built.

1)

3

{1, 3, 5, 2, 1}

Returns: 2

We want to have at least three buildings with the same number of floors. The best way to reach this goal is to build one floor on building #0 and one floor on building #4 (0-based indices). After these changes, buildings #0, #3, and #4 will have two floors each.

2)

1

{43, 19, 15}

Returns: 0

3)

3

{19, 23, 9, 12}

Returns: 15

4)

12

{25, 18, 38, 1, 42, 41, 14, 16, 19, 46, 42, 39, 38, 31, 43, 37, 26, 41, 33, 37, 45, 27, 19, 24, 33, 11, 22, 20, 36, 4, 4}

Returns: 47

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.

View Code

題目意思是給定一堆樓高度的 List 為?heights ，需要在這些樓里選擇 M 棟高度相同的樓，如果沒夠足夠相同高度的樓，就加高一些樓層使得滿足需求。求至少需要加高多少層數樓。

最直接的解題思路：

排序所有樓層，分別計算加高到某一樓層需要的總層數，取出其中最少的數字。

假設所有樓層有：{19, 23, 9, 12} 4棟樓。要在其中取 M= 3 棟相同的樓層，排序后的序列為：

{9, 12, 19, 23}

則從第 3 棟開始考慮增加樓層，即將 9， 12 增加至 19 ， 共需增加 19*3 - (9 + 12 + 19) = 17 層

在第 4 棟樓層(23)開始增加：共需增加 23*3 - (12 + 19 + 23) = 15 層

答案是 15

Java 寫的實現：

importjava.util.ArrayList;importjava.util.Collections;importjava.util.List;public classBuildingHeightsEasy {public static voidmain(String[] args) {

BuildingHeightsEasy bh= newBuildingHeightsEasy();int M = 3;int[] heights = {19, 23, 9, 12} ;int total =bh.minimum(M, heights);

System.out.println(total);

}public int minimum(int M, int[] heights) {if (M == 1) {return 0;

}

List list = new ArrayList();for(Integer cost : heights) {

list.add(cost);

}

Collections.sort(list);

Integer total=Integer.MAX_VALUE;for (int i = M - 1; i < list.size(); i++) {int sum =getSumValue(M, i, list);if (sum

total=sum;

}

}returntotal;

}public int getSumValue(int M, int end, Listlist) {int sum = 0;for (int i = end - M + 1; i < end + 1; i++) {

sum+=list.get(i);

}int value =list.get(end);return value * M -sum;

}

}

Java 在 int 數組轉換為 List 和 sum List 值等方便會比較繁瑣。

Python 的實現：

classBuildingHeightsEasy(object):defminimum(self, M, heights):if M == 1 : return0

heights=list(heights)

heights.sort()

total= M * heights[len(heights)-1]for i in range(M-1,len(heights)):

sumValue= M * heights[i] - sum(heights[i-M+1:i+1])

total= sumValue if sumValue < total elsetotalreturntotal

M= 3heights= (19, 23, 9, 12)

bh=BuildingHeightsEasy()print bh.minimum(M,heights)

Python 內置了很豐富的函數，特別是 sum 函數和 list 的切片功能。

結語留空。

總結

以上是生活随笔為你收集整理的topcoder java_Topcoder 练习小记，Java 与 Python 分别实现。的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。