给定一个长度为 n 的数组,数组中的元素表示每个木头的长度,木头可以在任意位置截断。从这些木头中取出至少 k 个长度都为 m 的木头。请问 m 最大是多少。
数据范围:数组长度满足 ,木头长度满足 ,
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; } }