求最小值的最大可能,使用二分法。
确定思路后最重要的是找到left,right分别是什么。
本题中因为题面明确说“分裂成两堆新的石子数量都大于等于1的石子堆”,故left初始值为1;
另,因为本题死分石子,故最小值的最大值为初始数组中的最小值,再分下去只能小于等于初始数组中的最小值,故right初始值为排序后的a[0];
计算过程为:
1)计算出mid;
2)根据mid计算当前石子可被分为sum堆(每堆与mid相除即为可分裂为几个);
3)sum与m比较,若sum>=m,说明mid值太小,将left改为mid;若sum<m,说明mid值太大,将right值改为mid - 1;
4)循环计算,直到right=left
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 * @param m long长整型 * @param a int整型vector * @return int整型 */ int solve(int n, long long m, vector<int>& a) { // write code here sort(a.begin(), a.end()); if (m == n) { return a[0]; } int left = 1; int right = a[0]; int mid = 0; while (left < right) { int sum = 0; if ((right + left) % 2 == 0) { mid = (right + left) / 2; } else { mid = (right + left + 1) / 2; } for (int i = 0; i < n; i++) { sum += (a[i] / mid); } if (sum >= m) { left = mid; } else { right = mid - 1;; } } return left; } };