关于二分法的一些总结
二分搜索
【下面的程序都是在区间[l,r]上查找x，默认数据顺序非递减】
一、二分查找区间内某个数字的下标
二分查找区间内某个数字的下标（存在且唯一），不存在返回-1：
int search(int l,int r,int x)
{
int mid;
while (l<=r)
{
mid=(l+r)>>1;
if(a[mid]==x) return mid;
if(a[mid]<x) l=mid+1;
else r=mid-1;
}
return -1;
}
这应该是最好写的二分
二、查询区间内<=x的最大值
查询区间内<=x的最大值（有多个最大值时返回最靠右的坐标）：
int search(int l,int r,int x)
{
int mid;
while (l<r)
{
mid=(l+r+1)>>1;
if(a[mid]<=x) l=mid;
else r=mid-1;
}
return l;
}
二分过程不多说，注意两点：
- 假设要在[l,r]上查询那么建议传进去的参数是l-1.r，这样如果返回值为l-1则说明不存在<=x的值，或者可以选择在二分前选判断，确定存在解时再二分。
- mid=(l+r+1)>>1而不是mid=(l+r)>>1，如果取后一种方式的话，假设区间缩小到2、3，此时mid=2，此时如果a[mid]<=x成立那么l=mid，这样会变成死循环，所以要+1再除2。
三、查询区间内>=x的最小值
查询区间内>=x的最小值（有多个最小值时返回最靠左的坐标）：
int search(int l,int r,int x)
{
int mid;
while (l<r)
{
mid=(l+r)>>1;
if(a[mid]>=x) r=mid;
else l=mid+1;
}
return l;
}
只是条件变成了r=mid和l=mid+1，因此mid要改成mid=(l+r)>>1，否则也会死循环。查询区间[l,r]则传参l,r+1，同样返回值为r+1时为无解。
这样只要控制好上下界和取中间的条件就可以二分了。
四、实数二分
实数上的二分比较好写，根据题目要求的精度控制一下边界就好，一般不会出现死循环的情况的。
while (fabs(r-l)>EPS)//EPS是题目要求的精度
{
mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
五、练习题目
1. 网线主管
题目描述及输入输出
输入输出：
输入：
4 11
8.02
7.43
4.57
5.39
输出：
2.00
题目思路及代码
思路：这里就是直接进行二分，判断是否符合结果！！！注意特殊情况进行判断，也就是不能分割的情况。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll maxn=1e5+10;
const ll maxm=1e8+10;
const ll mod=1e9+7;
ll n,m;
ll a[maxn];
ll mx;
ll check(ll x){
ll res=0;
for(int i=1;i<=n;i++){
res+=a[i]/x;
}
return res;
}
int main(){
cin>>n>>m;
ll sum=0;
for(int i=1;i<=n;i++){
double s;
cin>>s;
a[i]=s*100;
mx=max(a[i],mx);
sum+=a[i];
}
if(m>sum){
printf("0.00");
return 0;
}
ll l=1,r=mx;
ll ans=0;
while(l<r){
ll mid=(l+r+1)>>1;
if(check(mid)>=m){
l=mid;
}
else{
r=mid-1;
}
}
printf("%.2lf",l*1.0/100);
return 0;
}
2. 借教室
题目描述及输入输出
输入输出：
输入：
4 3
2 5 4 3
2 1 3
3 2 4
4 2 4
输出：
-1
2
题目思路及代码
思路： 首先是区间修改，这里用差分进行求解，通过二分进行缩小结果区间！！！
二分及差分代码
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll maxn=1e5+10;
const ll maxm=1e8+10;
const ll mod=1e9+7;
int line[1000010], l[1000010], r[1000010], d[1000010], change[1000010],sum[1000010];
int n,m;
int check(int x)
{
memset(change,0,sizeof(change));
for (int i = 1; i <= x; i++)
{
change[l[i]]+=d[i];
change[r[i]+1]-=d[i];
}
for (int i = 1; i <= n; i++)
sum[i]=sum[i-1]+change[i];
//obj 2抹平差分数组
for (int i = 1; i <= n; i++)
if(sum[i]>line[i])return false;
//obj 3什么情况下是发生了问题？
return true;
}
int main(){
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &line[i]);
for (int i = 1; i <= m; i++)
scanf("%d %d %d", &d[i], &l[i], &r[i]);
if(check(n))
{
printf("0");
return 0;
}
int l = 1, r = n, mid=0;
while(l<r)
{
mid = (l + r) >> 1;
if(!check(mid))//obj 5
r=mid;
else
l=mid+1;
//cout<<l<<" "<<r<<" "<<check(mid)<<endl;
}
printf("-1\n");
printf("%d", l);
return 0;
}
树状数组代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll maxn=1e5+10;
const ll maxm=1e8+10;
const ll mod=1e9+7;
int line[1000010], l[1000010], r[1000010], d[1000010], t[1000010],ti[1000010];
int n,m;
int lowbit(int n){
return n&(-n);
}
void update(int x,int val){
for(int i=x;i<=n;i+=lowbit(i)){
t[i]+=val;
ti[i]+=val*x;
}
}
int getsum(int x){
int sum=0;
for(int i=x;i;i-=lowbit(i)){
sum+=(x+1)*t[i]-ti[i];
}
return sum;
}
int pan(){
int ans=0;
for(int i=1;i<=n;i++){
int sum=getsum(i)-getsum(i-1);
if(sum>line[i])return 0;
}
return 1;
}
int main(){
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &line[i]);
int f=0;
for (int i = 1; i <= m; i++)
{
scanf("%d %d %d", &d[i], &l[i], &r[i]);
update(l[i],d[i]);
update(r[i]+1,-d[i]);
if(f)continue;
if(!pan()){
f=i;
}
}
if(f)printf("-1\n%lld",f);
else{
printf("0");
}
return 0;
}
六、推荐给大家的一段话
“遇事不决可问春风，春风不语即随本心”的意思是：对一件事犹豫不决，就问春风该如何做，春风给不出答案，就凭自己本心做出决断。“遇事不决可问春风，春风不语即随本心”一句出自网络作家“烽火戏诸侯”的《剑来》，其原文是：“遇事不决，可问春风。春风不语，遵循己心”。
