B3880 [信息与未来 2015] 买木头

从最小的可能解，到最大的可能解之间，通过二分查找，验证每一个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 l[10001], s[10001], n, m;

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

int main() {
  cin >> n >> m >> l[1] >> s[1];
  for (int i = 2; i <= n; i++) {
    l[i] = (l[i-1]*37011+10193)%10000+1;
    s[i] = (s[i-1]*73011+24793)%100+1;
  }
  
  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;
}