《二分王国的三大秘技竞赛必会》》小侦探小明已经学会了普通二分、左边界、右边界。这一天老师交给他三张神秘任务卡 第一种找“第一个 ≥ target”1、 故事宝藏街1 3 5 7 92、 任务找第一个 ≥ 6 的数答案应该是7位置33、 思想超级重要 不是找“等于” 而是找第一个满足条件的4、 模板最常用int lower_bound(int a[], int n, int target) { int left 0, right n - 1; int ans n; // 默认不存在 while(left right) { int mid (left right) / 2; if(a[mid] target) { ans mid; right mid - 1; // 往左找更小的满足条件 } else { left mid 1; } } return ans; }5 一句话记忆满足条件 → 往左缩 第二种找“第一个 target”1、 故事1 3 5 7 9 找第一个 5 的数答案7位置32、 思想 比第一种更严格一点必须 target3、 模板int upper_bound(int a[], int n, int target) { int left 0, right n - 1; int ans n; while(left right) { int mid (left right) / 2; if(a[mid] target) { ans mid; right mid - 1; } else { left mid 1; } } return ans; }4、 一句话记忆严格满足 → 往左缩 第三种二分答案1、 故事小明遇到一个超级难题 有一堆木头要切成 k 段 每段长度尽量长问最大长度是多少2、 普通想法 枚举所有长度 ❌太慢3、 神奇思路二分答案 答案在一个范围里长度 ∈ [1, 最大木头长度] 我们可以猜一个长度 mid 看看“行不行”4、 核心思想竞赛灵魂 把问题变成这个答案“可不可以” 如果可以 → 尝试更大 如果不行 → 变小5、 模板bool check(int mid) { // 判断 mid 是否可行 } int binary_search_answer() { int left 1, right 1000000; int ans 0; while(left right) { int mid (left right) / 2; if(check(mid)) { ans mid; left mid 1; // 尝试更大 } else { right mid - 1; } } return ans; }6、 一句话记忆能行 → 往更大试 不行 → 往更小试7、⚖️ 三大变形对比总结类型本质特点lower_bound第一个 ≥常用于区间upper_bound第一个 处理重复二分答案猜答案竞赛核心 最终大脑模型 所有二分题本质只有两种 类型1找位置数组里找数✔ lower_bound / upper_bound / 左右边界 类型2找答案答案满足单调性✔ 二分答案最重要 竞赛口诀找位置 → 看大小 找答案 → 看能否课后训练竞赛真题 第1题切木头入门之王1、 故事小明有很多木头8 5 6他想切成k 5 段一样长的小木头 问每段最长是多少2、 思考关键 长度越大 → 能切的段数越少 长度越小 → 能切的段数越多 出现单调性可以二分3、 图解假设 mid 38 → 2段 5 → 1段 6 → 2段 总共 5 ✔ 可以4、 check函数bool check(int mid) { int cnt 0; for(int i 0; i n; i) cnt a[i] / mid; return cnt k; }5、 完整代码#include iostream using namespace std; int a[100005]; int n, k; bool check(int mid) { int cnt 0; for(int i 0; i n; i) cnt a[i] / mid; return cnt k; } int main() { cin n k; for(int i 0; i n; i) cin a[i]; int left 1, right 1000000000; int ans 0; while(left right) { int mid (left right) / 2; if(check(mid)) { ans mid; left mid 1; } else { right mid - 1; } } cout ans endl; } 第2题分牛经典1、 故事有一排牛棚1 2 8 12 17要放3头牛 要让牛之间距离尽量大2、 思考 距离越大 → 能放的牛越少 距离越小 → 能放的牛越多 又是单调性3. 图解mid 7放1 → 下一个 ≥8 → 8 ✔ 放8 → 下一个 ≥15 → 17 ✔ 共3头 ✔4、 check函数贪心bool check(int mid) { int cnt 1; int last a[0]; for(int i 1; i n; i) { if(a[i] - last mid) { cnt; last a[i]; } } return cnt k; }5、 完整代码#include iostream #include algorithm using namespace std; int a[100005]; int n, k; bool check(int mid) { int cnt 1, last a[0]; for(int i 1; i n; i) { if(a[i] - last mid) { cnt; last a[i]; } } return cnt k; } int main() { cin n k; for(int i 0; i n; i) cin a[i]; sort(a, a n); int left 0, right a[n-1]; int ans 0; while(left right) { int mid (left right) / 2; if(check(mid)) { ans mid; left mid 1; } else { right mid - 1; } } cout ans endl; } 第3题抄书问题经典1、 故事有一排书10 20 30 40要给2个人抄 每人连续抄书注意是按照顺序连续抄书一个人抄完另外一个才能抄书。 求最大工作量最小2、 思考 工作量越小 → 需要的人越多 工作量越大 → 人数越少 单调成立4、 图解mid 60102030 60 一个人✔ 40 一个人 ✔ 共2人 ✔5、 check函数bool check(int mid) { int cnt 1, sum 0; for(int i 0; i n; i) { if(sum a[i] mid) { cnt; sum a[i]; } else { sum a[i]; } } return cnt k; } 完整代码#include iostream using namespace std; int a[100005]; int n, k; bool check(int mid) { int cnt 1, sum 0; for(int i 0; i n; i) { if(sum a[i] mid) { cnt; sum a[i]; } else { sum a[i]; } } return cnt k; } int main() { cin n k; for(int i 0; i n; i) cin a[i]; int left 0, right 1000000000; int ans right; while(left right) { int mid (left right) / 2; if(check(mid)) { ans mid; right mid - 1; // 找更小 } else { left mid 1; } } cout ans endl; } 三题核心总结题目check含义方向切木头能切够吗✔ 往大找分牛能放下吗✔ 往大找抄书人够吗✔ 往小找 关键理解 二分答案其实就是猜答案 判断对不对
GESP5级C++考试语法知识（十、二分算法（二））
《二分王国的三大秘技竞赛必会》》小侦探小明已经学会了普通二分、左边界、右边界。这一天老师交给他三张神秘任务卡 第一种找“第一个 ≥ target”1、 故事宝藏街1 3 5 7 92、 任务找第一个 ≥ 6 的数答案应该是7位置33、 思想超级重要 不是找“等于” 而是找第一个满足条件的4、 模板最常用int lower_bound(int a[], int n, int target) { int left 0, right n - 1; int ans n; // 默认不存在 while(left right) { int mid (left right) / 2; if(a[mid] target) { ans mid; right mid - 1; // 往左找更小的满足条件 } else { left mid 1; } } return ans; }5 一句话记忆满足条件 → 往左缩 第二种找“第一个 target”1、 故事1 3 5 7 9 找第一个 5 的数答案7位置32、 思想 比第一种更严格一点必须 target3、 模板int upper_bound(int a[], int n, int target) { int left 0, right n - 1; int ans n; while(left right) { int mid (left right) / 2; if(a[mid] target) { ans mid; right mid - 1; } else { left mid 1; } } return ans; }4、 一句话记忆严格满足 → 往左缩 第三种二分答案1、 故事小明遇到一个超级难题 有一堆木头要切成 k 段 每段长度尽量长问最大长度是多少2、 普通想法 枚举所有长度 ❌太慢3、 神奇思路二分答案 答案在一个范围里长度 ∈ [1, 最大木头长度] 我们可以猜一个长度 mid 看看“行不行”4、 核心思想竞赛灵魂 把问题变成这个答案“可不可以” 如果可以 → 尝试更大 如果不行 → 变小5、 模板bool check(int mid) { // 判断 mid 是否可行 } int binary_search_answer() { int left 1, right 1000000; int ans 0; while(left right) { int mid (left right) / 2; if(check(mid)) { ans mid; left mid 1; // 尝试更大 } else { right mid - 1; } } return ans; }6、 一句话记忆能行 → 往更大试 不行 → 往更小试7、⚖️ 三大变形对比总结类型本质特点lower_bound第一个 ≥常用于区间upper_bound第一个 处理重复二分答案猜答案竞赛核心 最终大脑模型 所有二分题本质只有两种 类型1找位置数组里找数✔ lower_bound / upper_bound / 左右边界 类型2找答案答案满足单调性✔ 二分答案最重要 竞赛口诀找位置 → 看大小 找答案 → 看能否课后训练竞赛真题 第1题切木头入门之王1、 故事小明有很多木头8 5 6他想切成k 5 段一样长的小木头 问每段最长是多少2、 思考关键 长度越大 → 能切的段数越少 长度越小 → 能切的段数越多 出现单调性可以二分3、 图解假设 mid 38 → 2段 5 → 1段 6 → 2段 总共 5 ✔ 可以4、 check函数bool check(int mid) { int cnt 0; for(int i 0; i n; i) cnt a[i] / mid; return cnt k; }5、 完整代码#include iostream using namespace std; int a[100005]; int n, k; bool check(int mid) { int cnt 0; for(int i 0; i n; i) cnt a[i] / mid; return cnt k; } int main() { cin n k; for(int i 0; i n; i) cin a[i]; int left 1, right 1000000000; int ans 0; while(left right) { int mid (left right) / 2; if(check(mid)) { ans mid; left mid 1; } else { right mid - 1; } } cout ans endl; } 第2题分牛经典1、 故事有一排牛棚1 2 8 12 17要放3头牛 要让牛之间距离尽量大2、 思考 距离越大 → 能放的牛越少 距离越小 → 能放的牛越多 又是单调性3. 图解mid 7放1 → 下一个 ≥8 → 8 ✔ 放8 → 下一个 ≥15 → 17 ✔ 共3头 ✔4、 check函数贪心bool check(int mid) { int cnt 1; int last a[0]; for(int i 1; i n; i) { if(a[i] - last mid) { cnt; last a[i]; } } return cnt k; }5、 完整代码#include iostream #include algorithm using namespace std; int a[100005]; int n, k; bool check(int mid) { int cnt 1, last a[0]; for(int i 1; i n; i) { if(a[i] - last mid) { cnt; last a[i]; } } return cnt k; } int main() { cin n k; for(int i 0; i n; i) cin a[i]; sort(a, a n); int left 0, right a[n-1]; int ans 0; while(left right) { int mid (left right) / 2; if(check(mid)) { ans mid; left mid 1; } else { right mid - 1; } } cout ans endl; } 第3题抄书问题经典1、 故事有一排书10 20 30 40要给2个人抄 每人连续抄书注意是按照顺序连续抄书一个人抄完另外一个才能抄书。 求最大工作量最小2、 思考 工作量越小 → 需要的人越多 工作量越大 → 人数越少 单调成立4、 图解mid 60102030 60 一个人✔ 40 一个人 ✔ 共2人 ✔5、 check函数bool check(int mid) { int cnt 1, sum 0; for(int i 0; i n; i) { if(sum a[i] mid) { cnt; sum a[i]; } else { sum a[i]; } } return cnt k; } 完整代码#include iostream using namespace std; int a[100005]; int n, k; bool check(int mid) { int cnt 1, sum 0; for(int i 0; i n; i) { if(sum a[i] mid) { cnt; sum a[i]; } else { sum a[i]; } } return cnt k; } int main() { cin n k; for(int i 0; i n; i) cin a[i]; int left 0, right 1000000000; int ans right; while(left right) { int mid (left right) / 2; if(check(mid)) { ans mid; right mid - 1; // 找更小 } else { left mid 1; } } cout ans endl; } 三题核心总结题目check含义方向切木头能切够吗✔ 往大找分牛能放下吗✔ 往大找抄书人够吗✔ 往小找 关键理解 二分答案其实就是猜答案 判断对不对
