第一节： 二分
定义：（一遍恒比这个值小一遍恒比这个值大为了找出这个值第一次或最后一次出现的位置所以用二分）
注意，这里的有序是广义的有序，如果一个数组中的左侧或者右侧都满足某一种条件，而另一侧都不满足这种条件，也可以看作是一种有序（如果把满足条件看做 
，不满足看做 ，至少对于这个条件的这一维度是有序的）。换言之，二分搜索法可以用来查找满足某种条件的最大（最小）的值。
整数二分模版
bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)//第一次出现
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)//最后一次出现
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}浮点数二分模版
bool check(double x) {/* ... */} // 检查x是否满足某种性质
double bsearch_3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}二分总结
首先熟记模版，二分包括check函数和while（l<r）的循环 最后要l
接着了解二分用途：
用来确定满足某一条件的最值（即最先或最后出现）
然后完成程序：
写这个代码的步骤：
1.确定满足条件是什么-->即check函数
满足条件返回true
否则返回false
2.确定答案的左右边界
l=
r=
3.左右边界靠循环逼近找到答案
写while（l<r){
int mid=
if(check(mid)){
}
else{
}
}
紫色行的做优边界如何修改看check里面规定什么情况满足条件
然后由紫色行定黄色mid在整数二分里怎么变
两种可能
下取整
mid=l+r>>1;
上取整：
mid=l+r+1>>1
4.最后答案是l
二分例题：
例题一：分巧克力
儿童节那天有 K位小朋友到小明家做客。
小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 N块巧克力，其中第 i 块是 Hi×Wi的方格组成的长方形。
为了公平起见，小明需要从这 N块巧克力中切出 K块巧克力分给小朋友们。
切出的巧克力需要满足：
- 形状是正方形，边长是整数
- 大小相同
例如一块 6×5 的巧克力可以切出 6 块 2×2的巧克力或者 2 块 3×3 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？
输入格式
第一行包含两个整数 N 和 K。
以下 N行每行包含两个整数 Hi 和 Wi。
输入保证每位小朋友至少能获得一块 1×1 的巧克力。
输出格式
输出切出的正方形巧克力最大可能的边长。
数据范围
1≤N,K≤105
1≤Hi,Wi≤105
输入样例：
2 10
6 5
5 6输出样例：
2题目解析：
首先由每一位小朋友所得巧克力边长相同-->我们要求的就是满足条件的一个值（最大边长）-->对于每一块巧克力豆花粉乘若干块这个边长的小巧克力
所以关键就是求一个值
所以很容易想到二分算法
开始进行二分操作
1.check函数
我们要满足的是巧克力分出来的个数>=小朋友数
所以需要满足的条件是for循环所有巧克力划分出来的子块数求和>=小朋友数
每一块巧克力在确定划分边长是x时能划分出（h[i]/x)*(w[i]/x)个子块
2.写左右边界
最终答案介于1~105
l=1
r=1e5
3.写while循环
while（l<r）{
int mid=l+r+1>>1;//由下面的l，r变化-->确定mid上取整
if(check(mid)){
//划分块多了那么需要增加边长
l=mid;
}
else{
r=mid-1;
}
}
4.输出答案l
cout<<l;
完整代码
#include<bits/stdc++.h>
using namespace std;
int n,k;//n块巧克力，k个小朋友
const int N=1e5+6;
int h[N];//所有巧克力的长
int w[N];//所有巧克力的宽
typedef long long int ll;
bool check(int x){
ll res=0;
for(int i=0;i<n;i++){
res+=(ll)(h[i]/x)*(w[i]/x);
}
if(res>=k)return true;
return false;
}
int main(){
cin>>n>>k;
for(int i=0;i<n;i++)cin>>h[i]>>w[i];
//进行二分（先定l，r然后不断通过check函数（满足什么条件）来找到想要的值）
//巧克力边长至少为1
int l=1;
//巧克力边长最多为10的5次方
int r=1e5;
while(l<r){
int mid=l+r+1>>1;
if(check(mid)){
l=mid;
}
else r=mid-1;
}
cout<<l;
return 0;
}