#M8025. 二分答案
二分答案
二分答案
和二分查找中查找某个元素第一次出现的位置和最后一次出现的位置相似,二分答案是求最小化答案 或最大化答案,所以写法上和二分查找一脉相承。
选择一种二分查找的写法,加以扩展即可。
//最小化答案
bool check(int x) {
... // 计算 y
return y >= C; //x大y大
return y <= C; //x小y大
}
int find(int x) {
int L = 下界-1, R = 上界+1;
while (L + 1 < R) {
int mid = (L + R) / 2;
if (check(mid)) { // 将二分查找的 比较判断改为根据check函数返回值判断
R = mid;
} else {
L = mid;
}
}
return R;
}
//最大化答案
bool check(int x) {
... // 计算 y
return y <= C; //x小y小
return y >= C; //x小y大
}
int find(int x) {
int L = 下界-1, R = 上界+1;
while (L + 1 < R) {
int mid = (L + R) / 2; // 若用位运算写作 L + R >> 1;
if (check(mid)) {
L = mid;
} else {
R = mid;
}
}
return L;
}