首页 > 代码库 > Wood Cut
Wood Cut
Note:
审题: 注意也有一种情况是: 一共有N个元素,要k个,但有不需要从每一个块去取, 只需要从其中的一些取。所以这里end开始应该取最大的element。而且有可能完全取不到,所以start应该从0开始取。剩下的和copy book那道题想法一致。
public class Solution { /** *@param L: Given n pieces of wood with length L[i] *@param k: An integer *return: The maximum length of the small pieces. */ public int woodCut(int[] L, int k) { // write your code here if (L == null || L.length == 0) { return 0; } int start = 0; int end = L[0]; for (int i = 0; i < L.length; i++) { if (end < L[i]) { end = L[i]; } } //System.out.println(end + " " + start); while (start + 1 < end) { int mid = start + (end - start) / 2; int tmp = countPiece(L, mid); //System.out.println(tmp + " " + start + " " + end + " " + mid); if (countPiece(L, mid) >= k) { start = mid; } else { end = mid; } } //System.out.println(start + " " + end); if (countPiece(L, end) >= k) { return end; } return start; } private int countPiece(int[] L, int maxlen) { int count = 0; for (int i = 0; i < L.length; i++) { count += L[i] / maxlen; } return count; } }
Wood Cut
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。