二分查找相关算法应用

在二分查找相关算法简介里我们编写并证明了二分查找算法，以及二分查找上界和下界算法。这篇文章举几个简单的实例来说明其在实际问题上的应用。

一般提起二分查找相关算法的应用，都需要一个有序数组，这样我们才能每次砍掉一半的查找区间。但其实二分查找相关算法可以在所有单调（Monotonic）的区间上应用。有序数组就是一个单调区间。对于一个非递减数组 $Arr$，在 $i < j$ 时，一定有 $Arr[i] \leq Arr[j]$。

我们把数组求值改成函数求值，一样可以应用二分查找相关算法，我们举几个例子来详细说明。

实例：2594. Minimum Time to Repair Cars

You are given an integer array $ranks$ representing the ranks of some mechanics. $ranks_i$ is the rank of the $i^{th}$ mechanic. A mechanic with a rank $r$ can repair n cars in $r \times n^2$ minutes.

You are also given an integer cars representing the total number of cars waiting in the garage to be repaired.

Return the minimum time taken to repair all the cars.

Note: All the mechanics can repair the cars simultaneously.

一般遇到这种求最大最小值的题目，第一时间想到的算法是 DP 或贪心。但是这道题很显然没有什么局部最优解和子问题，因此 DP 和贪心算法都不适用。这里我们考虑，修车所需的时间 $time$，和所有机械工能修好的车的最多数量 $N$ 之间，是什么关系？

从题目来看，对于等级为 $ranks_i$ 的机械工，他修好 $n$ 辆车所需要的时间 $time$ 为： $$time = ranks_i \times n^2$$ 那么我们给定 $time$，他能修好的车的最大数量 $n_i$ 为： $$n_i = \lfloor\sqrt\frac{time}{ranks_i}\rfloor$$ $ranks_i$ 是确定的，因此 $time$ 和 $n_i$ 之间是单调递增关系，即 $time$ 变大，$n_i$ 不变或变大。

如果我们有 $k$ 个修理工，那么所有机械工能修好的车的最多数量 $N=\sum_{i=0}^{k-1}n_i$，显然 $time$ 和 $N$ 之间也是单调递增关系。我们用代码计算这个函数：

bool canRepair(const std::vector<int>& ranks,
               const int cars,
               const long long timeLimit) {
  std::intmax_t repairedCars = 0;
  for (const auto rank : ranks) {
    repairedCars += getMaximumCarsCanRepairWithinTime(rank, timeLimit);
    if (repairedCars >= cars) {
      return true;
    }
  }
  return false;
}

std::intmax_t getMaximumCarsCanRepairWithinTime(const int rank,
                                                const long long time) {
  return static_cast<std::intmax_t>(std::sqrt(static_cast<long double>(time) /
                                              static_cast<long double>(rank)));
}

有了这个单调函数，我们回到题目：给定 $cars$ 和 $ranks$，确定最小的修理时间。换句话说，就是找到最小的修理时间 $time$，使得修好的车的最多数量 $N \geq cars$，同时 $time$ 和 $N$ 之前存在单调递增关系，这显然是一个二分查找下界问题，因此解法就很明确了：

long long repairCars(const std::vector<int>& ranks, const int cars) {
  const auto maxRank = *std::max_element(ranks.cbegin(), ranks.cend());
  long long left = 1;
  // We let the mechanic with hightest rank to repair all cars, 
  // getting the maximum possible time.
  long long right = static_cast<long long>(maxRank) * cars * cars + 1;

  while (left < right) {
    const auto mid = (right - left) / 2 + left;
    if (canRepair(ranks, cars, mid)) {
      // We can repair more than required cars in mid time.
      // So minimum time required is <= mid.
      right = mid;
    } else {
      left = mid + 1;
    }
  }

  return left;
}

实例：2226. Maximum Candies Allocated to K Children

You are given a 0-indexed integer array candies. Each element in the array denotes a pile of candies of size candies[i]. You can divide each pile into any number of sub piles, but you cannot merge two piles together.

You are also given an integer k. You should allocate piles of candies to k children such that each child gets the same number of candies. Each child can be allocated candies from only one pile of candies and some piles of candies may go unused.

Return the maximum number of candies each child can get.

对于这道题，我们假设每个孩子得到的糖果数量是 $candyNumberPerChild$，因为糖果的分布 $candies$ 是确定的，那么随着 $candyNumberPerChild$ 变大，可以得到 $candyNumberPerChild$ 个糖果的孩子数量 $childWithCandyNumber$ 是不变或减少的；反之，随着 $candyNumberPerChild$ 变小，可以得到 $candyNumberPerChild$ 个糖果的孩子数量 $childWithCandyNumber$ 是不变或增加的。也就是说，$candyNumberPerChild$ 与 $childWithCandyNumber$ 之间是单调递减的。

根据题目，我们需要满足 $k$ 个孩子都能得到同样数量的糖果。给定 $candyNumberPerChild$，判断该条件是否满足的代码如下：

bool canDivideCandies(const std::vector<int>& candies,
                      const long long childrenNumber,
                      const int targetCandyNumberPerChild) {
  if (targetCandyNumberPerChild == 0) {
    return true;
  }
  long long gotCandiesChildrenNumber = 0;

  for (const int candie : candies) {
    gotCandiesChildrenNumber += candie / targetCandyNumberPerChild;
  }

  return gotCandiesChildrenNumber >= childrenNumber;
}

容易想到，若 canDivideCandies 返回 false，则 $candyNumberPerChild$ 太大了；反之，则 $candyNumberPerChild$ 可能太小了。显然，这是一个二分查找上界问题。因此解法就很明确了：

int maximumCandies(std::vector<int>& candies, const long long k) {
  int left = 0;
  int right = *std::max_element(candies.cbegin(), candies.cend()) + 1;

  while (left < right) {
    const int mid = (right - left) / 2 + left;
    if (canDivideCandies(candies, k, mid)) {
      // We can divide mid candies to every child.
      // So maximum candies per child is >= mid.
      // Note we use mid + 1 here, 
      // since upper bound should make canDivideCandies to return false.
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return left - 1;
}

这里注意最后返回了 left - 1。这是因为，根据上界的定义，left 是我们需要的 $candyNumberPerChild + 1$，因此返回 left - 1。