二分

二分法是一种暴力枚举的优化版，它可以使时间复杂度大大减少，从而达到优化的效果。它同时又是一种典型的分治思想的应用。
核心思想是把待求解问题分为两部分，每一部分分别求解。
解决具有单调性质的题
暴力枚举O（N），二分O(log N)、
二分代码
整数：

while(l<r){
mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid+1;
}
//找最小的1（左） 如000000 111111
while(l<r){
mid=(l+r+1)/2;
if(check(mid)) l=mid;
else r=mid-1;
}
//找最大的1（右）如111111 000000

小数版

while(r-l>eps){
mid=(l+r)/2;
if(f(mid)>0) r=mid;
else l=mid;
}

（6）例题：派
先枚举扫一遍，再二分，求得正确答案。（暴力可以 但是时间复杂度不行）

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 1000
#define M 1000
using namespace std;
int n,f,a[N];
bool check(int x){    //寻找答案区间 
int s=0;
for(int i=1;i<=n;i++) s+=a[i]/x;
if(s>=f) return true;
return false;
}
int main(){
cin>>n>>f;
f++;
int sum=0;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
}
int l=0,r=sum/f;
//二分模板求答案 
while(l<r){
int mid=(l+r+1)/2;
if(check(mid)) l=mid;
else r=mid-1;
}
cout<<l<<endl;
}