P8647 [蓝桥杯 2017 省 AB] 分巧克力

从最小的可能解，到最大的可能解之间，通过二分查找，验证每一个mid是否为解。
二分的过程是这样的：
定义变量ans，储存当前优解。定义闭区间[left, right]，代表程序当前正在此闭区间内寻找答案（寻找潜在的比ans更优的解）。
令mid = (left + right)/2
若mid为解，则ans = max(ans, mid), left = mid + 1. 此时我们更新了最优解，同时在最优解的右侧寻找潜在的更优解。
若mid不为解，则right = mid - 1. mid不是解，因此我们在mid左边寻找更优解。
重复上述过程，直到left > right时跳出循环，ans即为最优解。

#include <iostream>
using namespace std;

int h[100001], w[100001], n, k;

bool check(int x) {
  int s = 0;
  for (int i = 1; i <= n; i++) {
    s += (h[i]/x) * (w[i]/x);
  }
  return s >= k;
}

int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> h[i] >> w[i];
  }
  
  int low = 1, high = 10000, ans = 0;
  while (low <= high) {
    int mid = low + (high-low)/2;
    if (check(mid)) {
      low = mid + 1;
      ans = max(ans, mid);
    } else {
      high = mid - 1;
    }
  }

  cout << ans << endl;
  return 0;
}