Loading... 二分搜索算法的重要性不需要多说, 一张图即可证明:  这个是我比较薄弱的地方, 所以专门来补一下. # 模板 首先第一部分是模板, 仅考虑离散的搜索空间, 那么任何搜索空间都可以用闭区间$[l,r]$去表示, 以下是一个二分搜索的例程: ```cpp int binary_search(int x) { int l = 0, r = a.size() - 1; //在闭区间内搜索 int mid; while (l <= r) { mid = l + (r - l) / 2; if (a[mid] == x) //注意,该算法返回的是任意一个符合要求的结果 return mid; // 下标索引 if (ok(mid, x)) l = mid + 1; else r = mid - 1; //每次区间大小都必定会变动 //所以循环条件是l<=r(即区间大小>=1). } return -1; } ``` 只要修改一下判断条件, 即可用于二分答案等任务. 代码中重要的部分均已使用注释来强调. 其核心思路就是, 如果当前点更大, 那么就往左侧去搜索$mid--$; 如果更小, 就往右侧去搜索$mid++$; 在碰到目标时返回. 每次检测之后, 如果没有找到目标, 搜索空间都会**跳过**$mid$而移动到一侧, 是**必然会缩小**的. 因此我们循环终止条件可以设定为$[l,r].size()\ne 0$, 并不会陷入死循环. 注意到以上程序仅能判断可行解是否存在, 那么如何实现$lower\_bound$这种找到解的一段的目的呢? 思路上比较简单, 我们仍然在闭区间$[l,r]$上搜索, 目前需要改变的仅仅是在找到目标值时候的处理方式. 应当从以往的直接返回变为向更小端查找以期找到可能存在的更小下标. 需要注意的是, 由于不立即返回, 那么每一次找到不小于$x$(这是$lower\_bound$的应有语义, 也可以变为与$x$严格相等)的值时, 需记录当前下标再进行向左侧的迭代. 代码如下: ```cpp int lower_bound(int x) { int l = 0, r = a.size() - 1; int ans = -1; while (l <= r) { int mid = l + (r - l) / 2; if (a[mid] >= x) r = mid - 1, ans = mid; else l = mid + 1; } return ans; } ``` 在这个基础上, 如果要实现$upper\_bound$也很简单, 只要将判断时的**等于号从大于部分移动到小于部分上**即可(以上代码中即为去掉第8行的$=$). # 例题 ## [洛谷P2678 [NOIP2015 提高组] 跳石头](https://www.luogu.com.cn/problem/P2678) NOIP2015的d2t1, 记忆犹新啊. ### 题意 线段$[0, L]$上有$n$个点, 最多去掉$m$个, 要求任意两点(包括两个端点和最近点)之间距离最小值最大, 求这个值. 所有涉及**最X值最X**的统称为最值的最优化, 如果考察可行解的范围是单调的话, 应当使用**二分答案+检验**的方式解决. 事实上, 所有**可行解位于一个连续范围, 并且容易检验一个解是否可行**的问题, 都可以使用二分答案在$O(check*log值域)$的时间复杂度下来解决. 本题即为一个典例. ### 分析 二分答案+检验的做法是无疑的. 只要知道checker怎么写就可以了. 在check$mid$的过程中, 我们可以从左边出发, 遇到距离已走过的点不远于$mid$的点就去掉, 然后看看去掉的点个数是否不超过$m$即可. 为什么可以贪心去掉点呢? 因为**接下来的路程只和已经走过的路程的右端点有关, 所以贪心去掉当前点, 就是贪心地将已走过路程的右端点向左推**, 肯定是最优的. ### 代码 ```cpp #include <bits/stdc++.h> using namespace std; #define mp(x, y) make_pair(x, y) #define FOR(x, y, z) for (int x = y; x <= z; x++) typedef long long ll; #define N 50004 int l, n, m; // 距离 岩石数量 最多移走数量 vector<int> a; bool ok(int dis, int mov) { int cnt = 0; int last = a.front(); for (int i = 1; i < a.size(); i++) if (a[i] - last < dis) cnt++; else last = a[i]; return cnt <= mov; } int f() { int l = 1, r = 1000000000; int ans; while (l <= r) { int mid = l + (r - l) / 2; if (ok(mid, m)) l = mid + 1, ans = mid; else r = mid - 1; } return ans; } int main() { cin >> l >> n >> m; a.push_back(0); FOR(i, 1, n) { int t; cin >> t; a.push_back(t); } a.push_back(l); cout << f(); return 0; } ``` 二分整个算法是简单的, 每道题的难度在于$checker$的写法上, 接下来看一道题, 也是我整理二分的动机: ## [[Codeforces Round #762 (Div. 3)] D. New Year's Problem](https://codeforces.com/contest/1619/problem/D) ### 题意 $n$个朋友$m$家商店, 要给每个朋友选礼物, 每个朋友对每个商店的礼物都有特定的喜爱值. 只能去$n-1$家商店, 每家商店买礼物的数量不限, 求朋友中的最小喜爱值最大可以是多少. ### 分析 显然二分答案. 问题是$checker$的写法. 这里要注意到$n-2$家商店是可以选择$n-2$个朋友的最大喜爱值所在商店的, 那么就只需要判断是否存在一家商店能够满足**至少**$2$**位朋友的喜爱值不小于**$mid$就行了. 另外注意检查一下每个人的最大喜爱值要不小于$mid$. ### 代码 ```cpp #include <bits/stdc++.h> using namespace std; #define mp(x, y) make_pair(x, y) #define FOR(x, y, z) for (int x = y; x <= z; x++) typedef long long ll; int t; int m, n; // shops, friends #define N 100005 vector<vector<int>> a; int maxx[N]; bool ok(int small) { for (int i = 0; i < m; i++) { int cnt = 0; for (int j = 0; j < n; j++) if (a[i][j] >= small) cnt++; if (cnt >= 2) return true; } return false; } int f() { int minn = *min_element(maxx + 1, maxx + n + 1); ll l = 1, r = 1e9 + 1; int ans = -1; while (l <= r) { ll mid = l + (r - l) / 2; if (mid <= minn && ok(mid)) ans = mid, l = mid + 1; else r = mid - 1; } return ans; } int main() { cin >> t; while (t--) { cin >> m >> n; // visit at most n-1 shops memset(maxx, 0, sizeof(maxx)); a.clear(); int ans = 0; FOR(i, 1, m) { vector<int> tmp; tmp.clear(); FOR(j, 1, n) { int x; cin >> x; tmp.emplace_back(x); if (x > maxx[j]) maxx[j] = x; } a.push_back(tmp); } cout << f() << endl; } return 0; } ``` © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用，请随意赞赏