求最小值的最大可能,使用二分法。
确定思路后最重要的是找到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;
}
};

京公网安备 11010502036488号