给定一个长度为 n 的数组,数组中的元素表示每个木头的长度,木头可以在任意位置截断。从这些木头中取出至少 k 个长度都为 m 的木头。请问 m 最大是多少。
数据范围:数组长度满足 ,木头长度满足 ,
class Solution { public: int cutWood(vector<int>& a, int k) { int right = 0; for(auto i : a) right = max(right, i); return binary(a, k, 1, right + 1); } private: int stickNum(vector<int>& a, int k) { int ret = 0; for(auto i : a) ret += i / k; return ret; } int binary(vector<int>& a, int k, int left, int right) { int mid = 0; while(left < right) { mid = left + (right - left) / 2; if(stickNum(a, mid) < k) right = mid; else left = mid + 1; } return left - 1; } };将求解满足段数的最大木棒长度,改成使小于段数最小木棒长度,转换成upper_bound的形式。然后再将索引位置减一即可。
# -*- coding: utf-8 -*- # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param a int整型一维数组 # @param k int整型 # @return int整型 # class Solution: """ 题目: https://www.nowcoder.com/practice/707d98cee255448c838c76918a702be0?tpId=196&tqId=40513&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title= 参考: 大神:山山ks 算法: 本题考查的是我们以长度m切割每根木头,判断是否能切割出大于等于k根长度为m的木头 1. 对于m的选取,我们采用二分法,在区间[1, max(a)]中寻找 2. 若切割之后,长度为m的木头数量小于k,说明m选大了,right = mid - 1;否则,我们缩小区间为[mid, right]。 复杂度: 时间复杂度:O(nlogn + nlogx),n为a的长度,x为max(a) 空间复杂度:O(n) """ def cutWood(self, a, k): # write code here a.sort() left, right = 1, a[-1] n, m = len(a), 0 while left < right: mid = left + (right - left + 1) / 2 count = 0 for i in range(n - 1, -1, -1): if a[i] < mid: break count += a[i] / mid if count >= k: left = mid else: right = mid - 1 return left if __name__ == "__main__": sol = Solution() # a, k = [1, 2, 3, 4, 5], 3 # a, k = [1, 2, 3, 4, 5], 5 a, k = [1, 2, 3, 4, 5], 7 res = sol.cutWood(a, k) print res
class Solution { public: // 判断是否能够切割出k个m长度的木头 bool canCut(vector<int>& a, int k, int m) { int cnt = 0; for (auto num: a) { cnt += num / m; if (cnt >= k) return true; } return false; } // 二分,先排序,然后判断中间值是否满足 int cutWood(vector<int>& a, int k) { sort(a.begin(), a.end()); int l = a[0], r = a[a.size() - 1]; while (l <= r) { int mid = (l + r) / 2; // 如果能够切割出k个mid长度的木头,则在右半区间取木头大小 if (canCut(a, k, mid)) { l = mid + 1; } else { r = mid - 1; } } return r; } };
import java.util.*; public class Solution { /** * 二分法 */ public int cutWood (ArrayList<Integer> a, int k) { Collections.sort(a, Comparator.reverseOrder()); int left = a.get(a.size() - 1), right = a.get(0); while (left < right) { int mid = left + (right - left + 1) / 2; if (canCut(a, mid, k)) { left = mid; } else { right = mid - 1; } } return left; } private boolean canCut(ArrayList<Integer> a, int m, int k) { if (k == 0) return true; for (int i = 0; i < a.size() && a.get(i) >= m; i++) { int cur = a.get(i); if (cur >= m) { while (cur >= m) { cur -= m; k--; if (k <= 0) return true; } } else { return false; } } return false; } }