分石子
最优解
看到要使得最小值最大，则想到二分答案。
二分这个最小值，现在判断是否可以分出m份大于等于这个最小值的石堆。直接枚举每一堆石子然后看能分出几堆满足条件的石堆即可。
二分次数上界为,每次检查的复杂度为
,总的时间复杂度
只使用了常数个临时变量，空间复杂度
int solve(int n, long long m, vector<int> &a){
assert(a.size() == n);
int l = 1, r = 1e9;
for(int i = 0; i < n; ++i) r = min(r, a[i]);
int ans = 1;
while(l <= r){
int mid = (r+l)/2;
long long sum = 0;
for(int i = 0; i < n; ++i) sum += a[i]/mid;
if(sum < m) r = mid-1;
else ans = mid, l = mid+1;
}return ans;
}
查看25道真题和解析