企业官网建设流程全解析

前言

二分搜索一般分普通查找和二分答案两种，

上篇介绍了二分查找，

本文介绍二分答案

上篇

简介

二分答案（Binary Search on Answer）是一种在答案的可能范围内通过二分搜索来寻找最优解的算法思想。它不直接在数据上进行搜索，而是对问题的答案进行猜测，然后验证这个猜测是否可行，并根据验证结果不断缩小答案范围，最终找到最优解。

该算法的适用前提是问题具有单调性：如果某个值是可行的解，那么比更大（或更小）的值也必然具有某种一致的可行性（例如所有大于的值都可行，或所有小于的值都可行）。算法通过维护答案的左右边界，每次取中间值并调用一个判断函数来检查是否可行，然后根据单调性调整边界，直到找到最优解。

时间复杂度为O(log⁡(答案范围)×判断函数的复杂度)。这意味着即使答案范围很大，也能通过对数级别的猜测次数快速逼近最优解。

二分答案的优点是能够将“求最值”的问题转化为“给定一个值，判断是否可行”的问题，从而简化思考难度。它的主要缺点是需要问题具备单调性，且判断函数必须能够高效实现。该算法广泛应用于各种优化问题，如求最大值的最小化（如让最大值尽可能小）、求最小值的最大化（如让最小值尽可能大）、以及一些经典问题如木材切割、跳石头、机器人行走等。

代码框架

bool check(int mid) { // 用这个函数来检查 mid 是否是可行的答案 } int binarySearch() { int ans = -1, l = 1, r = n; // 答案、左右边界 while (l <= r) { int mid = (l + r) >> 1; if (check(mid)) { // 如果求最小值就尝试更小的答案 r = mid - 1, ans = mid; // 否则尝试更大的答案 l = mid + 1, ans = mid; } else { // 与上面相反 } } return ans; // 返回答案 }

例题

洛谷上没查到，只能到别的OJ上找了，

各位可以找一下

这次没链接

题目描述

小华被大林叫去砍树，他需要砍倒米长的木材。现在，小华弄到了一个奇怪的伐木机。伐木机工作过程如下：小华设置一个高度参数（米），伐木机升起一个巨大的锯片到高度，并锯掉所有的树比高的部分（当然，树木不高于 h 米的部分保持不变）。小华就得到树木被锯下的部分。
例如，如果一行树的高度分别为 20、15、10 和 17 米，小华把锯片升到 15 米的高度，切割后树木剩下的高度将是 15、15、10 和 15 米，而小华将从第 1 棵树得到 5 米，从第 4 棵树得到 2 米，共得到 7 米木材
小华非常关注生态保护，所以他不会砍掉过多的木材。这正是他为什么要尽可能高地设定伐木机锯片的原因。帮助小华找到伐木机锯片的最大的整数高度，使得他能得到的木材至少为米。换句话说，如果再升高 1 米，则他将得不到米木材

输入格式

第 1 行 2 个整数和，表示树木的数量，表示需要的木材总长度。
第 2 行个整数，表示每棵树的高度，值均不超过。保证所有木材长度之和大于，因此必然有解

输出格式

一行一个整数，表示砍树的最高高度

从题目可知要求答案尽量要大，

则二分最大高度（～），

再写一个函数判断能否得到米的木材

时间复杂度为答案范围

不会爆。

Code

1.带注释详解版

#include <iostream> #include <algorithm> using namespace std; using ll = long long; const int MAXN = 1e6 + 5; ll n, m, a[MAXN]; // n m a[] 如题面所示 bool check(ll h) { // check() 函数 ll sum = 0; // 所得到的木材总和 for (int i = 1; i <= n; i++) { if (a[i] >= h) sum += a[i] - h; // 计算 } return (sum >= m); // 达到要求 } ll binarySearch(ll m) { // 二分答案 ll ans, l = 1, r = 2e9; while (l <= r) { ll mid = (l + r) >> 1; // 折半 if (check(mid)) { // 答案可行 l = mid + 1, ans = mid; // 往更大的搜 } else { r = mid - 1; // 往更小的搜 } } return ans; } int main() { cin >> n >> m; // 输入 for (int i = 1; i <= n; i++) { cin >> a[i]; } cout << binarySearch(m) << endl; // 输出 return 0; }

2.无注释纯享版

#include <iostream> #include <algorithm> using namespace std; using ll = long long; const int MAXN = 1e6 + 5; ll n, m, a[MAXN]; bool check(ll h) { ll sum = 0; for (int i = 1; i <= n; i++) { if (a[i] >= h) sum += a[i] - h; } return (sum >= m); } ll binarySearch(ll m) { ll ans, l = 1, r = 2e9; while (l <= r) { ll mid = (l + r) >> 1; if (check(mid)) { l = mid + 1, ans = mid; } else { r = mid - 1; } } return l; } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; } cout << binarySearch(m) << endl; return 0; }

感谢观看！

有问题欢迎指出