TB椰程 TypeBuddy 打字搭子

二分答案

CSP-J · 编程模板 · 片段 · cpp · 难度 4/5 · 共 346 字

答案单调时二分答案，用 check 判定可行性

  • 二分
  • 单调性

前置内容

正文

// ── 二分答案 ──
// 把「求最小可行解」变成判定题
// 前提：check(x) 关于 x 单调
int l = 1, r = n, ans = -1;
while (l <= r) {
    int mid = l + (r - l) / 2;
    if (check(mid)) {
        // mid 可行：记下答案
        // 再试试更小的
        ans = mid;
        r = mid - 1;
    } else {
        // 不可行：答案只会更大
        l = mid + 1;
    }
}
printf("%d", ans);
// 与二分查找的区别：
// 二分的是「答案」不是下标

CSP-J · 编程模板的其它内容

打字首页 · 词库画廊 · 编程打字 · 指法入门 · 天梯榜 · 数据分析 · 班级课堂 · 关于我们
椰程 TypeBuddy 打字搭子 —— 键盘指法练习 · 单词记忆 · 班级课堂 · 在线 PK