【笔记】二分

二分分为二分查找和二分答案。

二分查找

每次查询或询问的结果：

• 找到，结束；
• 找不到，答案所在范围缩小一半。如果小了就查找大的那一半，如果大了就查找小的那一半。

查找次数为对数级。

前提：序列有序。

二分查找可以解决的问题：

• 大于等于 \(x\) 的最小值是哪个？大于等于 \(x\) 的有多少个？
• 小于等于 \(x\) 的最大值是哪个？小于等于 \(x\) 的有多少个？
• 如果多个值与 \(x\) 相等，有多少个？
• 如果找不到 \(x\)，与 \(x\) 最接近的是几？

模板题：Luogu P2249 查找

此题有虽然有序，但是有相同元素，如果每次查找 \(a[mid]\) $\color{red} \ge $ 目标那么 \(R=mid\)，不能舍弃相同的，否则 \(L=mid+1\)，直接跳过所有比目标小的。

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1e6+10;
int n,m,q;
int a[maxn];
int bfind(int tar){int l=1,r=n,mid;while(l<r){mid=(l+r)/2;if(a[mid]>=tar) r=mid;else l=mid+1;}if(a[l]==tar) return l;return -1;
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=m;i++){scanf("%d",&q);printf("%d ",bfind(q));}return 0;
}

这个二分查找中，如果找到了那么 \(L,R,mid\) 将会指向同一个位置，找一个输出即可。

变式：小于等于 \(x\) 中的最大值（如果多个和 \(x\) 相等，返回最后一个）。

如果 \(a[mid]\) \(\color{red} \le\) 目标那么 \(l=mid\)，否则 \(r=mid-1\)。

但是这样会出现死循环，因为下面的 \(mid-1\) 了所以执行一万次 \(l\) 也都会小于 \(r\)，因此上面要把 \(1\) 加回来，\(mid=\frac{l+r+1}{2}\)。

模板总结

找大于等于 \(x\) 的下标最小值：\(a_{mid} \ge x\)，\(r=mid\)；\(a_{mid} < x\)，\(l=mid+1\)。

int bfind(int tar){int l=1,r=n,mid;while(l<r){mid=(l+r)/2;if(a[mid]>=tar) r=mid;else l=mid+1;}if(a[l]==tar) return l;else return -1;
}

找小于等于 \(x\) 的下标最大值：\(a_{mid} \le x\)，\(l=mid\)；\(a_{mid} > x\)，\(r=mid-1\)，同时 \(mid=(l+r+1)/2\)。

int bfind(int tar){int l=1,r=n,mid;while(l<r){mid=(l+r+1)/2;if(a[mid]<=tar) l=mid;else r=mid-1;}if(a[l]==tar) return l;else return -1;
}

Luogu P1102 A-B 数对

遍历每个 \(a_i\)，找 \(a_i+c\) 出现了几次。

出现了几次可以用两种方法解决：

• 分别找下标最小值和最大值（上文）
• 用桶记录

注意不是有序的，记得 sort。

极端数据下答案会到 \(10^{10}\)，需要开 long long。

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=2e5+10;
int n,c;
long long cnt;
int a[maxn];
int bfindmin(int tar){int l=1,r=n,mid;while(l<r){mid=(l+r)/2;if(a[mid]>=tar) r=mid;else l=mid+1;}if(a[l]==tar) return l;else return -1;
}
int bfindmax(int tar){int l=1,r=n,mid;while(l<r){mid=(l+r+1)/2;if(a[mid]<=tar) l=mid;else r=mid-1;}if(a[l]==tar) return l;else return -1;
}
int main(){scanf("%d%d",&n,&c);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}sort(a+1,a+1+n);for(int i=1;i<=n;i++){int ans1,ans2;ans1=bfindmin(a[i]+c);if(ans1!=-1){ans2=bfindmax(a[i]+c);cnt+=(ans2-ans1+1);}		}cout<<cnt;return 0;
}

二分答案

二分答案：一些东西加起来的值需要满足某个条件，求其中的最大值最小是多少或最小值最大是多少。

Luogu P1873 [COCI 2011/2012 #5] EKO / 砍树

从 \(1\) 到最高树的高度进行二分锯子的高度答案，因为要求锯片尽可能高所以套模板二。

#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
const int maxn=1e6+10;
int n,m,maxx;
int a[maxn];
int bfind(){int l=1,r=maxx,mid,sum;while(l<r){sum=0;mid=(l+r+1)/2;for(int i=1;i<=n;i++){if(a[i]>mid)sum+=a[i]-mid;}if(sum>=m) l=mid;else r=mid-1;}return l;
}
signed main(){scanf("%lld%lld",&n,&m);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);maxx=max(maxx,a[i]);}printf("%lld\n",bfind());return 0;
} 

Luogu P2440 木材加工

把上题代码的-改成/就过了。

#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
const int maxn=1e5+10;
int n,k,maxx;
int a[maxn];
int bfind(){int l=0,r=maxx,mid,sum;while(l<r){sum=0;mid=(l+r+1)/2;for(int i=1;i<=n;i++){if(a[i]>mid)sum+=a[i]/mid;}if(sum>=k) l=mid;else r=mid-1;}return l;
}
signed main(){scanf("%lld%lld",&n,&k);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);maxx=max(maxx,a[i]);}printf("%lld\n",bfind());return 0;
} 

Luogu P1314 [NOIP2011 提高组] 聪明的质监员

题目比较绕，给了两个数学公式。我们二分 \(W\)，然后分别按公式求解每个询问的答案。这里要注意，二分的时候因为不知道 \(y\) 比 \(s\) 大是正确答案还是 \(y\) 比 \(s\) 小是正确答案，所以可以在每次二分的时候记录 \(|y-s|\) 的最小值，或者在最后输出的时候再去查一下另一种情况。并且在求解数学公式的时候，爆搜的复杂度是 \(O(n^2 \log w)\)，过不了，可以发现题目中的数学公式全部是求和，所以需用前缀和优化为 \(O(n \log w)\)。

#include<iostream>
#include<cmath>
#include<cstdio>
#define int long long
using namespace std;
const int maxn=2e5+10;
const int maxs=1e18;
struct mine{int w,v;
}a[maxn];
int n,m,s;
int prv[maxn],prn[maxn],L[maxn],R[maxn];
int check(int mid){int y=0;for(int i=1;i<=n;i++){if(a[i].w>=mid){prn[i]=prn[i-1]+1;prv[i]=prv[i-1]+a[i].v;}else{prn[i]=prn[i-1];prv[i]=prv[i-1];}}for(int i=1;i<=m;i++){y+=(prn[R[i]]-prn[L[i]-1])*(prv[R[i]]-prv[L[i]-1]);}return y;
}
int bfind(){int l=0,r=1000000,mid,ans=maxs;while(l<r){mid=(l+r+1)/2;int t=check(mid);if(t>=s) l=mid;else r=mid-1;if(abs(s-t)<ans) ans=abs(s-t);}return ans;
}
signed main(){scanf("%lld%lld%lld",&n,&m,&s);for(int i=1;i<=n;i++){scanf("%lld%lld",&a[i].w,&a[i].v);}for(int i=1;i<=m;i++){scanf("%lld%lld",&L[i],&R[i]);}printf("%lld",bfind());return 0;
}

实数二分

与整数二分类似，但有几个点要注意：

• \(l<r\) 会死循环，正确写法：设题目要求保留 \(k\) 位，\(l<r-10^{-k-2}\)。
• \(l=mid+1\) 会跳过大量实数，正确写法：\(l=mid+10^{-k-2}\)。
• \(mid-x>=0\) 有时会因为精度问题导致不能正确判断，正确写法：\(mid-x>=10^{-k-2}\)。
• 如果是二分开方，要注意在 \((0,1)\) 之间的情况。

例：求算术平方根二分

正确写法 1：

#include<iostream>
using namespace std;
double x;
int main(){cin>>x;double l=-100000,r=100000,mid;while(l<r-0.0001){mid=(l+r)/2.0;if(mid*mid-x>=0) r=mid;else l=mid;}printf("%.2lf",l);return 0;
}

正确写法 2（此写法能更好避免精度问题）：

#include<iostream>
using namespace std;
double x;
int main(){cin>>x;double l=-100000,r=100000,mid;for(int i=1;i<=100;i++){mid=(l+r)/2;if(mid*mid-x>=0) r=mid;else l=mid;}printf("%.2lf",l);return 0;
}

相当于把 \([l,r]\) 划分成 \(2^{100} \approx 10^{30}\) 段，把循环次数固定，避免了 \(l<r-0.0001\) 这样写的精度问题。一般来说，循环 \(40\) 次的精度就足够了。