二分和一些算法的奇妙组合
二分在竞赛中经常作为60|80 -> 100的奇妙法宝，许多题目的AC的关键就是二分，因为二分可以几乎优化掉整整一维！（log2十亿都才20几，可以看成常数了），关键就是如何二分，如何看出题目的单调性，并且如何将二分出来的东西和其它的算法奇妙的结合利用
下面是列出一些经典例题
二分和搜索的结合
这题是qzqz机房经（du）典（liu）名题，特别放在第一篇(
1532: 黄维的表情包
经过上一轮的撕杀，小G成为黄维的同桌（自己定的规则当然是为了方便自己的），于是为了安抚广大没有成为黄维同桌的机房党的心，他P了一大堆黄维的表情包，并打算分享给众OIER们。现已知机房有N台电脑，小G列出了M个他要分享的表情包及其大小Ai（即需要下载的时间）。小G做为表情包的拥有者，他觉得要给同学们出个难题，他竟然把表情包放在了教师机上！！教师机的U盘口又被老师给禁用了，于是只能网络传输的方式！但是机房里为了防止大家当网瘾少年，早就改成了单线程传输！于是为了赶在老师上课之前传完所有表情包，机房党们迅速研究出了最佳策略，就是大家分别下载不同的表情包，之后再想办法共享！他们分了工，每个电脑同一时间只下载一个表情包，一个表情包也只需由一个电脑下载，这样做到了每个电脑下载速度相同且互不影响！因为机房党们有群，所以每个表情包只需由某一台电脑下载一次就能使整个机房的电脑普及。现在机房党们想知道最快能在多长时间内下载完成。
Input Format
第1行：两个整数N、M，分别代表机房的电脑数及需要下载的表情包数量。
第2行：M个整数，第i个整数表示Ai的值。
Output Format
一行一个整数，表示能下载完所有表情包的最短时间。
输入
2 3
1 2 3
输出
3
初看这题，诶这不就是小木棍吗，不就把特判已经拼接的长度值等于len的改成小于等于吗
然而你会惊奇的发现：TLE
因为小木棍是O(n)枚举最长能拼接的长度的，而且有很多重复长度可以用去重等玄学优化好多
而这题的长度几乎不重复，而且总和的可能很多，单纯O(n)枚举是不可能了
所以一个思路很自然的就出现了——二分len长度
？二分，单调性呢？
我们可以稍微观察一下题目的特点
观察发现，当我们选取一个传输的最长时间len, 这个len选的越长，就越可能在n台电脑的传输下完成传输
而选的越短，就越不可能
所以我们对每次选取的mid进行尝试传输，如果成功了，说明还能用更短的时间进行传输
r = len - 1
，如果失败了，说明答案需要用更长的时间
else l = len + 1;
根据这个性质，我们可以二分选取最长的传输时间，并进行搜索求解是否能够传成功
先上代码，再讲优化
#include <bits/stdc++.h>
using namespace std; int a[110], len, sum, n, m, l, r; int v[101], mg[101]; inline bool dfs(int len, int x, int leg, int nx) {//len表示当前能够传输的最长时间限制
//x表示当前是在用第几台电脑进行尝试传输
//leg表示当前已经分配好了多少大小的表情包
//nx记录上一次分配了哪一个表情包(排好序的) // cout << len << " " << x << " " << nx << " " << leg << endl; if (x == n && leg + len >= sum) return true;
//如果已经分好了n台电脑，或者说我剩下的所有表情包刚好能用一台电脑在限定的时间内传好 if (sum - leg > (n - x + 1) * len)//这边对剩下的所有表情包进行估价
//如果剩下的电脑全部拉满(全部都充分利用len的时间)
//都无法让剩下的表情包传输好，那么就没有继续搜的必要了，直接返回false return false; for (register int i = nx + 1; i <= m; i++)//枚举表情包 if (!v[i] && a[i] + mg[x] <= len) { mg[x] += a[i], v[i] = 1;//表情包加上a[i],把这个设为已经选过 if (dfs(len, x, leg + a[i], i)) { v[i] = 0, mg[x] -= a[i];//如果按照我已经选下去的方案这样继续组合下去能成功
//那么直接回溯，返回true return true; } mg[x] -= a[i], v[i] = 0;//回溯 } return dfs(len, x + 1, leg, 0);//所有方案都试过了，没法再用这台电脑传输东西了，就直接搜下一台电脑 } int main() { cin >> n >> m; for (int i = 1; i <= m; i++) { cin >> a[i]; l = max(a[i], l), sum += a[i];//选取左右端点 } r = sum; sort(a + 1, a + m + 1, greater<int>());//从大到小排序，这样能保证每次都先选出需要的时间最长进行传输
//并且我们可以记录一个nx，就是上一次传输第几个, 下一次选择传输用时比这个小的
//这样能保证每台电脑传输的东西一定是先大后小的，能排除掉很多冗余情况 while (l <= r) { len = (l + r) >> 1; if (dfs(len, 1, 0, 0)) r = len - 1; else l = len + 1; } cout << r + 1; return 0; }
速度贼快，某fun姥爷姬0ms过
P1314 聪明的质监员
https://www.luogu.com.cn/problem/P1314
题意概要
给你一些区间，给你一些w,v数组，让你算一个参数，计算选定的区间内，w[i]大于这个参数的个数乘上若w[i]大于这个参数,累加v[i]最后的总和。
最后算出所有区间的检验值之和，让检验值之和和标准值的差最小
思路
根据观察发现，W这个参数选的越大，最后计算的检验值越小，具有单调性
考虑二分参数W，统计前缀和，利用前缀和快速求出每个区间的检验值之和，更新答案并跟标准值进行比较
注意，这里的检验值和标准值之差的绝对值是一个先增后减的函数，是不符合我们二分的单调性的，
我们可以选择让我们所有二分出来的值都小于这个标准值，相当于把这个绝对值的函数从中间砍了一半
我们理由右半边的单调性计算就好了
代码里面有详细解释
Code：
#include<bits/stdc++.h> using namespace std; int n, m, L, R; long long ans = 999999999999, s;//答案有可能超过longlong,开一下比较保险 struct ss{ int l, r; }p[1000101]; struct st{ int w, v; }q[1000101]; long long cf[1000101], gs[1000101];
//cf是计算差分的数组，gs是计算个数的数组 long long check (int x) { memset(cf, 0, sizeof(cf)); memset(gs, 0, sizeof(gs));//每次二分完检验答案都要记得把变量和数组清空！！！！！ for (int i = 1; i <= n; i ++) { if(q[i].w >= x) { gs[i] = gs[i - 1] + 1; cf[i] = cf[i - 1] + q[i].v; } else { gs[i] = gs[i-1]; cf[i] = cf[i-1]; } }//统计前缀和 long long ss = 0; for (int i = 1; i <= m; i ++) { int l = p[i].l, r = p[i].r; ss += (long long)(cf[r] - cf[l - 1]) * (gs[r] - gs[l - 1]); }//计算 if (llabs(ss - s) < ans) ans = llabs(ss - s);//每次计算完更新答案 return s < ss; } int main() { cin >> n >> m >> s; for (int i = 1; i <= n; i ++) scanf("%d %d", &q[i].w, &q[i].v), L = min(L, q[i].w), R = max(R, q[i].w); for (int i = 1; i <= m; i ++) scanf("%d %d", &p[i].l, &p[i].r); while (L <= R) { int mid = (L + R) >> 1; if (check(mid)) L = mid + 1; else R = mid - 1; }//二分 cout << ans; return 0; }