二分答案（进阶）

两种实现方式

循环实现

while 循环中每次循环都是判断区间是否存在（是否合法）
$left<=right$ 就是一个临界的合法的区间

int BiSearch(int a[],int n,int x){int left = 0,right = n-1;while(left <= right){  //注意： = 不可少int mid = (left+right)/2;if(a[mid] == x)return mid;if(x > a[mid])left = mid +1 ;else right = mid - 1;}return -1;
}

递归实现

递归先写出口（什么时候结束）
$if(left>right)$ 代表不存在此区间，所以跳出递归

int BiSearch(int a[],int x,int left,int right)
{if(left > right) //注意不可有 = return -1;else{int mid = (left+right)/2;if(a[mid] == x)return mid;else if(a[mid] > x)return BiSearch(a,x,left,mid - 1);else  if(a[mid] < x)return BiSearch(a,x,mid + 1,right);}
}

求最大的最小值 或者 最小的最大值 都是典型的二分答案
同时看到 n 的范围在 $10^5$ , $n^2$ 肯定过不了, 只能是 $O(nlo{g}_{2}n)$ 或者 $O(\sqrt{n})$ 级别的算法, $O(nlo{g}_{2}n)$ 很有可能是二分

例题

例题 1

e.g. 给定n个正整数a [1…n ]，将这个序列从左到右划分成m段，
使得每段至少有一个数; 你需要让数字之和最大的那一段的数字和尽可能的小

思路如下：
使用f(x)表示划分的不超过x的段数，且f(x)<=m
f(x)<=m 表示划分成立，因为f(x)<m且它是正确答案肯定还可以把所划分的那些段数中的其他所含元素大于1的段数继续划分，使得其大于f(x),也就是:
若 f(x) 有解, 则能划分 f(x) 段, 必然也能划分 f (x)+1 段
同时若 f (x) 有解 ,必然 f (x)>=f (x+1), 因为此时 f (x+1) 的限制更松, 一段里面包含的元素个数肯定不大于 f (x) 时一段里面包含的元素个数, 所以 f (x)>=f (x+1) 必然成立

综上, f (x) 是单调不递增函数, 可以用二分答案

二分答案的过程, 肯定在[max(a[1… n]), sum(a[1… n])] 中
因为 x<max (a[1… n]) 的情况肯定不存在 (若存在, 则 x 肯定不是那个最大值 )
同时 x 最大不超过 sum[1… n ] (x 若超过 sum[1… n]), 则最多划分为 1 段

例题 2

e.g. 给定n个正整数a[1…n]和一个正整数k一座高度为k的塔b[1…k]满足:
b[1]*2<=b[2],b[2]*2<=b[3],b[3]*2<=b[4]…
你要从中选择一些数来叠很多座高度为k的塔，问最多能叠多少座塔
2 <=n<= 100000
2 <=k<= 30
1 <= a[i]<= $10^9$

思路如下:
设 bool 型的 f (x) 代表可以建成 x 座塔
若 f (x) 成立, 则 f (x-1) 必定成立
因为可以建成 x 座塔则必然可以减成 x-1 座塔 (多出来那一座不建即可)
所以 f (x) 为离散型的单调不增序列 (函数)
可以用二分答案做

但是在贪心部分有个需要注意
例如 a{1,2,3,4}, k = 2
建塔情况肯定不会是 b 1 { 1 , 2 } , b 2 { } b_1\{1,2\},b_2\{~~\} b1​{1,2},b2​{  } (这种情况只能建 1座塔)
建塔情况应该是 b 1 { 1 , 3 } , b 2 { 2 , 4 } b_1\{1,3\},b_2\{2,4\} b1​{1,3},b2​{2,4} (这种情况可以建 2座塔, 最多)

所以贪心的正确思路是
先把 a 升序排序
设可以建成 x 座塔, 则这 x 座塔的第一层, 一定是 a 的前 x 个数 (顺序不一定, 但一定是这些数), 依次放到 $b[\mathrm{1..}x]$ 中 (b 中存放第 i 座塔的最上层的数字)
然后依次看第 2 层到第 k 层
每层的选取是从 a 中未放到 b 中的数字中选取的(可能会有跳过不选取的)
然后若在每层的选取中使得选取的数超过了 a 的数量范围
则证明 f (x) = 0,
若直到 b[x] 被迭代到第 k 层, a 中的 n 个数仍未选完 (或者恰好选完)
则证明 f (x) = 1, 也就是可以建 x 座 k 层的塔

bool f(int x){for(int i = 1;i<=x;i++) b[i] = a[i];//第一层int now = x + 1;//选取到了a[now]个元素for(int i = 2;i<k;i++){  //第2到第k层for(int j = 1;j<=x;j++){  //每层从第1~x个铺设while(now<=n&&2*b[j] > a[now]){//a中n个元素未选取完，并且不满足建塔条件则继续选取//存放在b中的是目前每座塔最高层元素//a中now往后的是待选取元素，满足建塔条件即选取//选取后，该元素选取完毕，now++now ++;}if(now>n) return 0;b[j] =a [now ++]}}return 1;//到达这一步，说明可以建造x座塔
}

例题 3

e.g. 给定 n 个正整数 a[1… n]和 m 个正整数 b[1… m]; 在 n*m 个 a[i]+b[j]中，找到第 k 小的数 (不去重);
1<=n, m<= 100000
1<=k<=n*m
1<= a[i], b[i]<= $10^9$

设 f (x) 表示有多少对 i, j 满足 a[i]+b[j]<=x则f(x)<=f(x+1)
因为 a[i]+b[j]<x+1 的范围更大, 所包含的数字更多
则 f(x)是单调函数
我们需要找到最小的x，满足f(x)>=k 二分
给定 x，如何统计有多少对 i, j 满足 a[i]+b[j]<=x 将 a 和 b 都从小到大排序后双指针统计 (尺取法)

index	1	2	3	4	5	6
i	👇left
a[1… n]	1	3	5	7	9
b[1… m]	2	4	6	8	10	12
j						👆right

比如 x = 12
初始 i = 1, 移动 j
j = 6 时不满足 a[i]+b[j]<=x, j–
j = 5 时满足 a[i]+b[j]<=x 此时说明 j 前面的数仍然满足(count += 5),
则有 5 个满足该条件的了, i++

此时 i = 2, j = 5
不满足 a[i]+b[j]<=x, j–
j = 4, 满足 a[i]+b[j]<=x 此时说明 j 前面的数仍然满足 (count += 4)
则有 4 个满足该条件的了, i++

……

long long f(int x){long long count = 0;int j = m;for(int i = 1;i<=n;i++){while(j && a[i]+b[j]>x) j--;count += j ;}return count ;
}

附带一个二分答案洛谷题目练习

序列合并

题目描述

有两个长度为 $N$ 的单调不降序列 $A,B$，在 $A,B$ 中各取一个数相加可以得到 $N^2$ 个和，求这 $N^2$ 个和中最小的 $N$ 个。

输入格式

第一行一个正整数 $N$；

第二行 $N$ 个整数 $A_{1\dots N}$。

第三行 $N$ 个整数 $B_{1\dots N}$。

输出格式

一行 $N$ 个整数，从小到大表示这 $N$ 个最小的和。

样例 #1

样例输入 #1

3
2 6 6
1 4 8

样例输出 #1

3 6 7

提示

对于 $50\%$ 的数据，$N\le 10^3$。

对于 $100\%$ 的数据，$1\le N\le 10^5$，$1\le a_i,b_i\le 10^9$。

#include <bits/stdc++.h>
using namespace std;
const int MAXSIZE = 100005;
int n;
long long  a[MAXSIZE], b[MAXSIZE], num[MAXSIZE * 10];
//f(x)判断是否使得a*b的值中小于x的数量大于n
bool f(long long  x) { //小于等于x的和的个数long long cnt = 0;int j = n;for (int i = 1; i <= n; i++) {while (j && a[i] + b[j] > x) {j --;}cnt += j ;if (cnt >= n) return 1; //说明x是候选解}return 0;
}
int main() {cin >> n;for (int i = 1; i <= n; i++)  cin >> a[i];for (int i = 1; i <= n; i++)  cin >> b[i];//二分//f(x)= {0,0,0,…,0,1,1,1…};//找1的左边界long long l = a[1] + b[1], r = a[n] + b[n];while (l < r) { //左开右开区间long long mid = (l + r) / 2;if (f(mid) == 1) {r = mid;} else if (f(mid) == 0) {l = mid + 1;}}//此时l为1的左边界int cnt = 0;for (int i = 1; i <= n; i++) {if (a[i] + b[1] > l) break;for (int j = 1; j <= n; j++) {if (a[i] + b[j] <= l) num[cnt++] = a[i] + b[j];}}sort(num, num + cnt);for (int i = 0; i < n; i++) {cout << num[i] << " ";}return 0;
}