LC2226.每个小孩最多能分到多少糖果

思路：二分查找取代暴力遍历

一堆糖果只能拆，不能合并，那么只要逐个堆计算，当前堆可以满足多少个小孩是非常容易计算的，最后相加就行。
如果每个小孩对糖果的需求量很少，比如1人就要1个，那么可以满足的人数就越多。越是要的多，满足的人就越少。
逐个增加小孩对糖果的需求，直到恰好满足 k个小孩。

对于“每个小孩需要的糖果数量”这个区间而言，相当于取左边区间的右端点。（二分查找）

代码：

class Solution {
public:
  bool check(int per_candy, vector<int>& candies, long long k) {
      long long cnt = 0;
      for (int i = 0; i < candies.size(); i++) {
          cnt += (candies[i] / per_candy);
      }
      return cnt >= k;
  }
  int maximumCandies(vector<int>& candies, long long k) {
      // 小孩拿到的糖果越是少，越是容易满足
      // 逐步提升小孩拿到的糖果数量，直到恰好满足 k 个小孩为止
      // 对于"每个小孩可以获得的糖果数量"这个数组而言，相当于取左区间的右端点
      int n = candies.size();
      int left = 0, right = *max_element(candies.begin(), candies.end());
      while (left < right) {
          int mid = (left + right + 1) / 2;
          if (check(mid, candies, k)) {
              left = mid;
          } else {
              right = mid - 1;
          }
      }
      return right;
  }
};