二分问题
今天给大家解答的主要是关于二分的问题，这类问题主要分为三类：
1.整数二分
2.浮点数二分
3.二分答案
这三类问题总体思路接近，其中二分答案的考察次数最多，最容易考察大家对于二分的思考和解决。
整数二分就是在一个有序的数组中，寻找第k个数，关键是找到l和r的两个端点。
其实解决二分问题无非要明白几个方面：
1.check函数的确立，这个check函数主要就是return 题目要求的物件个数，如岩石数，树木个数等等。
2.left和right的转移，if（check（mid）>=k）right=mid else left=mid;这都是固定的套路，大家要通过题目要理解
3.循环条件是while（l+1！=r）则初始l减1，r+1.看最后输出是l还是r就看题目要求是第一个最小，还是最后一个最小即可。
4.⚠️初始要排序，二分答案建立在排序的基础上。
⭐️常见题型：矩阵数值问题、岩石距离（给出不同岩石之间的距离，去掉岩石变大距离）、花束问题。
5注意⚠️：如果输出的是l（最大部分）前面的check（mid）<=m。如果输出的是r，前面的check（mid）<=m。其实check哪边都无所谓，关键是输出l则l=mid那边要带等号，不然结果并不正确。
问题描述
情人节到了，妮妮学姐的追求者实在太多了，她一共有 n 个追求者，第 i 个追求者赠送了 ai 朵颜色相同的花朵。每个追求者赠送的花朵颜色都不同。为了卖掉这些花并将所得款项捐赠给希望小学，妮妮学姐决定将 k 朵颜色不同的花朵打包成一个花束。请问她最多可以打包成多少个花束？
输入格式
第一行输入两个整数 n 和 k，分别表示妮妮学姐的追求者数量和打包需要的花朵数。
第二行输入 n个整数 ai，表示每个追求者赠送的花朵数量。
数据范围保证：1≤n,k≤2×105，1≤ai≤109。
输出格式
输出一个整数表示妮妮学姐最多可以打包成多少个花束。
输入案例：
2 2
5 6输出案例：
5代码部分：
/*
前置知识：二分答案
解题思路： 该题的check()函数很简单，假设枚举答案为x，则至少要有x*k个
有效花朵数，通过这一点，我们只扫描一下原数组，统计出有效花朵数量num，
在将其与x*k比较即可。其余部分直接套用二分模板。
注意：开long long！
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
long long a[N],n,k,sum;
bool check(long long x) {
long long num = 0;
for(int i = 1; i <= n; ++ i) {
num += min(a[i],x);
}
return num/k >= x; //这里最好将k除过去，防止溢出
}
int main() {
ios::sync_with_stdio(false);
cin>>n>>k;
for(int i = 1; i <= n; ++ i) cin>>a[i],sum += a[i];
//如果你使用的二分模板和我一样，请注意将边界l左移一位，边界r右移一位，否则会取不到边界值。
long long l = 0,r = sum+1;
while(l +1 != r) {
long long mid = (l + r) >> 1;
if(check(mid)) l = mid;
else r = mid;
}
cout<<l;
}问题描述
一年一度的"跳石头"比赛又要开始了！
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走M 块岩石（不能移走起点和终点的岩石）。
输入描述
输入文件第一行包含三个整数L，N，M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。
接下来 N 行，每行一个整数，第 i 行的整数Di（0<Di<L）表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。
其中，0≤M≤N≤5×104，1≤L≤109
输出描述
输出只包含一个整数，即最短跳跃距离的最大值。
输入案例：
25 5 2
2
11
14
17
21输出案例：
4代码部分：
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4+9;
int n,m;
int L;
int a[N];
int check(int mid)
{
int ans=0,last=0;
for(int i=1;i<=n;i++)
{
if(a[i]-a[last]<mid) ans++;
else last=i;
}
if(L-a[last]<mid) ans++;
return ans;
}
int main()
{
cin>>L>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
int l=0,r=1e9+5;
while (l+1!=r)
{
int mid=(l+r)>>1;
if(check(mid)<=m) l=mid;
else r=mid;
}
cout << l <<'\n';
return 0;
}问题描述
肖恩有一大片农田，农田中有 N 个可以种植苹果树的位置。这些位置都分布在一条直线上，坐标是 x1,x2,⋯,xN 。肖恩得到了 M 个树苗，需要种到农田中的对应位置。
我们都知道两棵苹果树种的距离如果太近的话会互相争抢养分，导致两棵苹果树都会营养不良。所以肖恩认为相邻两棵苹果树之间的最近距离越大越好，那么请你帮肖恩算算最大的最近距离是多少？
输入描述
第一行输入两个整数 N 和 M ，两个数字的意义和题面中描述相同。
第二行输入 N 个数字，第 i个数字 xi 表示第 i个可以种植苹果树的位置。
数据保证 1≤N≤105,1≤M≤N,1≤xi≤109 。
输出描述
输出一个数字表示最大的最近距离。
输入案例：
5 3
1 3 4 8 9输出案例：
3代码部分：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int a[N];
int n,m;
//最近距离为多少时，最多能放多少棵树苗
int check(int x){
int count=1;
int lst = 1;
for(int i=2;i<=n;i++){
if((a[i]-a[lst])>=x){
count++;
lst=i;
}
}
return count;
}
//5443322
int main(){
//最近距离能放多少棵树苗（最大的最近距离）
//思考：距离为多少最多能放多少棵树苗
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
//未保证输入坐标是有序的，需要排序
sort(a+1,a+n+1);
int l=1,r=1e9;
//要确定枚举的是什么
while(l+1!=r){
int mid = (l+r)/2;
if(check(mid)<m)r=mid;
else l=mid;
}
cout <<l<<'\n';
return 0;
}问题描述
肖恩认为一般的乘法表不够美观，因为它是三角形的所以肖恩认为不够整齐。肖恩自己制作了一张矩形乘法表，对于一张 n×m 的矩形乘法表，肖恩会把 i×j 填充到矩形的第 i 行第 j 列的位置。现在，肖恩向你提问：在这张乘法表中，第 k 大的元素是多少？
矩形乘法表中第 k大元素是指将矩形乘法表中所有元素从小到大排列后的第 k 个元素。
输入描述
输入三个数字n,m,k ，每个数字的意义和问题描述中相同。
输入保证1≤n,m≤5×105,1≤k≤n×m 。
输出描述
输出一个数字表示第 k大的元素。
输入案例：
2 4 5输出案例：
4代码部分：
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll res;
ll n,m,k;
ll check(ll mid){
res=0;
for(int i=1;i<=n;i++)res+=min(m,mid/i);
return res;
}
int main()
{
cin>>n>>m>>k;
ll l=0;ll r=1e12;
while(l+1!=r){
ll mid=(l+r)>>1;
if(check(mid)>=k)r=mid;
else l=mid;
}
cout<<r<<'\n';
return 0;
}