今天去尝试了一下美团 AI 平台，两次面试连一起。但是两位面试官小哥都是做推荐的，我们互相都不了解对方怎么做的。于是乎就做算法题，讲论文（把不懂的人讲懂确实困难），然后全程小哥给我介绍他们部门情况，我就挂机听着。不管这家拿不拿得到，就当刷刷经验吧，也挺不错的。一共三道题目，前两道一个最长上升子序列，一道快速排序，就不讲了，都是原题。
题目描述
题目链接：
牛客网：分石子
牛牛有 n 堆石子堆，第 i 堆一共有 a[i] 个石子。
牛牛可以对任意一堆石子数量大于 1 的石子堆进行分裂操作，分裂成两堆新的石子数量都大于等于 1 的石子堆。
现在牛牛需要通过分裂得到 m 堆石子，他想知道这 m 堆石子的最小值最大可以是多少？
示例：
输入：
3,5,[3,5,6]
输出：
2
解释：
把5分裂成2和3
把6分裂成2和4
得到五堆石子[3,2,3,2,4]备注：
- $1 \le n \le 10^5, n \le m \le \sum{a_i}, 1 \le a_i \le 10^9$
- 第一个参数
n代表石子堆的个数 - 第二个参数
m表示需要得到的石子堆数。 - 第三个参数
vector a代表每堆石子堆的石子个数
题解
一拿到这个题目，就看出来这是一道二分答案的题目。
首先定义上下界 l = 1, r = min{a[i]} ，也就是说，每一堆个数最小值至少为 1 ，最多就是初始的时候最小的那堆个数。
然后对于 mid = (l + r) / 2 ，含义就是假设最终最小的那堆有 mid 个。我们求出初始时每一堆最多可以划分出多少个数全部大于等于 mid 的子堆，显然个数是 a[i] / mid 取整，记总堆数为 cnt。
如果 cnt < m ，那么说明 mid 太大了，你最多也不可能划分成 m 堆，所以更新 r = mid - 1 。如果 cnt > m ，那么说明 mid 太小了，你能划分的堆数大于了 m ，那么更新 l = mid + 1 。最后如果 cnt = m ，你就暂存一下答案，因为这时的 mid 是有可能成为最终答案的。但是 mid 还是可能太小了，因为 mid 稍微大一点 cnt 是不会变的，所以继续更新 l = mid + 1 。
最终返回暂存的答案 res 即可。注意这题的二分框架和之前做过的有所不同，在等号判断上得特别小心，我一开始没想清楚，错了好多次才通过的。
代码
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) {
typedef long long ll;
ll l = 1, r = *min_element(a.begin(), a.end()), res = 0;
while (l <= r) {
ll mid = l + (r - l) / 2;
ll cnt = 0;
for (auto x : a) {
cnt += x / mid;
}
if (cnt < m) r = mid - 1;
else {
l = mid + 1;
res = mid;
}
}
return res;
}
};关注公众号【算法码上来】，每日算法干货马上就来！
