首页 > 代码库 > Topcoder 练习小记，Java 与 Python 分别实现。
Topcoder 练习小记，Java 与 Python 分别实现。
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:BuildingHeightsEasyMethod:minimumParameters:int, int[]Returns:intMethod signature:int minimum(int M, int[] heights)(be sure your method is public)Limits Time limit (s):2.000Memory limit (MB):256Constraints-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.Examples0) 2{1, 2, 1, 4, 3}Returns: 0Note 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: 2We 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: 03) 3{19, 23, 9, 12}Returns: 154) 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: 47This 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.
题目意思是给定一堆楼高度的 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 写的实现：
import java.util.ArrayList;import java.util.Collections;import java.util.List;public class BuildingHeightsEasy { public static void main(String[] args) { BuildingHeightsEasy bh = new BuildingHeightsEasy(); 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<Integer> list = new ArrayList<Integer>(); 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) { total = sum; } } return total; } public int getSumValue(int M, int end, List<Integer> list) { int sum = 0; for (int i = end - M + 1; i < end + 1; i++) { sum += list.get(i); } int value =http://www.mamicode.com/ list.get(end); return value * M - sum; }}
Java 在 int 数组转换为 List 和 sum List 值等方便会比较繁琐。
Python 的实现：
class BuildingHeightsEasy(object): def minimum(self, M, heights): if M == 1 : return 0 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 else total return totalM = 3heights = (19, 23, 9, 12)bh = BuildingHeightsEasy()print bh.minimum(M,heights)
Python 内置了很丰富的函数，特别是 sum 函数和 list 的切片功能。
结语留空。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。