『算法-ACM 竞赛-二分算法』ACM-二分法-模板

// 在单调递增序列 a 中查找>=x 的数中最小的一个（即 x 或 x 的后继）
while (l < r) {
int mid = (l + r) / 2;
if (a[mid] >= x) r = mid; else l = mid + 1;
}

// 在单调递增序列 a 中查找<=x 的数中最大的一个（即 x 或 x 的前驱）
while (l < r) {
int mid = (l + r + 1) / 2;
if (a[mid] <= x) l = mid; else r = mid - 1;
}

// 实数域二分，设置 eps 法
while (l + eps < r) {
double mid = (l + r) / 2;
if (calc(mid)) r = mid; else l = mid;
}

// 实数域二分，规定循环次数法
for (int i = 0; i < 100; i++) {
double mid = (l + r) / 2;
if (calc(mid)) r = mid; else l = mid;
}

// 把 n 本书分成 m 组，每组厚度之和<=size，是否可行
bool valid(int size) {
int group = 1, rest = size;
for (int i = 1; i <= n; i++) {
if (rest >= a[i]) rest -= a[i];
else group++, rest = size - a[i];
}
return group <= m;
}

// 二分答案，判定“每组厚度之和不超过二分的值”时能否在 m 组内把书分完
int l = 0, r = sum_of_Ai;
while (l < r) {
int mid = (l + r) / 2;
if (valid(mid)) r = mid; else l = mid + 1;
}
cout << l << endl;