今天带着大家根据C++：第十讲二分查找-CSDN博客?继续讲一下二分的题目。
题目背景
出题是一件痛苦的事情！
相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！
题目描述
给出一串正整数数列以及一个正整数?C，要求计算出所有满足A?B=C?的数对的个数（不同位置的数字一样的数对算不同的数对）。
输入格式
输入共两行。
第一行，两个正整数?N,C。
第二行，N?个正整数，作为要求处理的那串数。
输出格式
一行，表示该串正整数中包含的满足A?B=C?的数对的个数。
输入 #1
4 1
1 1 2 3
输出 #1
3
说明/提示
对于?75%的数据，1≤N≤2000。
对于?100%的数据，1≤N≤2×105，0≤ai?<230，1≤C<230。
这一题将A-B=C转换成A-C=B，首先将A数组每个元素出现的次数统计起来，用map映射，最后将A数组每次减一个C，再将A数组扫一遍，将所有映射的次数和加起来就是答案。
看到数据规模后就应该想到是nlogn的算法或者n的，O(n)复杂度的算法可能不太好想，毕竟题中没有给规定数的大小，只是longint，这样如果是桶的思想可能就会爆掉，那么对于A-B=C这个式子来说，两个变量都在等号同侧，这样只能n方枚举，肯定T，那么我们考虑移项，则有A-C=B，这样两边分别都含变量，我们每次枚举A，这样问题就转换为寻找数组中元素为A-C的个数，白皮书上很明确的提到过这一技巧。二分即可。
#include<bits/stdc++.h>
using namespace std;
using namespace std;
typedef long long LL;
LL a[200001];
map<LL,LL> m;
int main() {
int n;
LL c;
LL ans=0;
cin >> n >> c;
for(int i=1;i<=n;i++) {
cin >> a[i];
m[a[i]]++;
a[i]-=c;
}
for(int i=1;i<=n;i++) ans+=m[a[i]];
cout << ans << endl;
return 0;
}
题目描述
虽然 Miss Medusa 到了北京，领了科技创新奖，但是她还是觉得不满意。原因是：他发现很多人都和她一样获了科技创新奖，特别是其中的某些人，还获得了另一个奖项——特殊贡献奖。而越多的人获得了两个奖项，Miss Medusa就会越眼红。于是她决定统计有哪些人获得了两个奖项，来知道自己有多眼红。
输入格式
第一行两个整数n,m，表示有n?个人获得科技创新奖，m?个人获得特殊贡献奖。
第二行?n?个正整数，表示获得科技创新奖的人的编号。
第三行m?个正整数，表示获得特殊贡献奖的人的编号。
输出格式
输出一行，为获得两个奖项的人的编号，按在科技创新奖获奖名单中的先后次序输出。
输入 #1
4 3
2 15 6 8
8 9 2
输出 #1
2 8
说明/提示
对于?60%的数据，0≤n,m≤1000，获得奖项的人的编号 <2×109；
对于?100%的数据，0≤n,m≤105，获得奖项的人的编号 <2×109。
输入数据保证第二行任意两个数不同，第三行任意两个数不同。
我是什么算法？
说白了就是：
暴搜！
但是，纯暴搜是肯定要超时的，所以我们要加一个小小的优化：
规则是这样的：
设a为科技创新奖，b为特殊贡献奖。
如果a[i]>b[j],那么a[i+1]也必定大于b[j]（我用的是升序排序），之后同理。
所以，出现这种情况时，j可以毫不犹豫地向后加，一直加到b[j]不小于a[i]为止。
然后判断一不一样就可以了。
这就是一个很简单，却很实用的优化，可以AC。
#include<bits/stdc++.h>
using namespace std;
int n,m;
map<int,bool> v;
int a[101000];
int b[101000];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=m;i++){
cin>>b[i];
v[b[i]]=true;
}
for(int i=1;i<=n;i++){
if(v[a[i]]){
cout<<a[i]<<" ";
}
}
return 0;
}
题目描述
Farmer John 建造了一个有 N（2≤N≤105) 个隔间的牛棚，这些隔间分布在一条直线上，坐标是 x1?,x2?,?,xN?（0≤xi?≤109）。
他的?C（2≤C≤N）头牛不满于隔间的位置分布，它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗，Farmer John 想把这些牛安置在指定的隔间，所有牛中相邻两头的最近距离越大越好。那么，这个最大的最近距离是多少呢？
输入格式
第?11?行：两个用空格隔开的数字?N?和?C。
第 2～N+1?行：每行一个整数，表示每个隔间的坐标。
输出格式
输出只有一行，即相邻两头牛最大的最近距离。
输入 #1
5 3
1
2
8
4
9
输出 #1
3
非常经典的一道二分答案模板题
什么是二分答案？简单地说，就是和二分查找相似，二分每个答案，然后对这个答案进行求证，看是否满足条件，然后再次进行左右区间查找，知道二分到单个点上
这一题，我们二分答案找每个牛棚之间的最大距离。
#include<bits/stdc++.h>
using namespace std;
int const N=1e5+5;
int a[N],n,m,l,r,mid;
bool C(int x){
int sum=1;
int last=1;
for(int i=2;i<=n;i++){
if(a[i]-a[last]>=x){
sum++;
last=i;
}
}
return sum>=m;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
l=0,r=1e9+5;
while(r-l>1){
mid=(l+r)/2;
if(C(mid)){
l=mid;
}
else{
r=mid;
}
}
cout<<l<<endl;
return 0;
}题目描述
有?N?条绳子，它们的长度分别为 Li?。如果从它们中切割出?K?条长度相同的绳子，这?K?条绳子每条最长能有多长？答案保留到小数点后?22?位(直接舍掉?22?位后的小数)。
输入格式
第一行两个整数?N?和?K，接下来?N?行，描述了每条绳子的长度 Li??。
输出格式
切割后每条绳子的最大长度。答案与标准答案误差不超过?0.010.01?或者相对误差不超过?1%1%?即可通过。
输入 #1
4 11
8.02
7.43
4.57
5.39
输出 #1
2.00
说明/提示
对于?100%的数据0<Li?≤100000.00,0<n≤10000,0<k≤10000
我们直接二分答案，区间的l取0、r取长度和，然后check时对每条长度除以二分的值向下取整，判断是否不小于k就行了。楼下基本是转换成整型进行二分，我这里直接对实型进行二分，然后输出时稍微处理就行了。
二分查找，设C(x)为=可以得到K条长度为x的绳子。
由于长度为L的绳子最多可以切出floor(L/x)段长度为x的绳子，因此C(x)=（floor(L/x)的总和是否大于等于K）由于1次循环可以缩小区间的一半，100次循环可以达到10^-30的精度，是绝对够了的。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
double a[N],l,r,mid;
int n,k;
int C(double x){
int ans=0;
for(int i=1;i<=n;i++){
ans+=(int)(a[i]/x);
}
return ans>=k;
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
l=0;r=1e9;
for(int t=0;t<100;t++){
mid=(r+l)*0.5;
if(C(mid)){
l=mid;
}
else{
r=mid;
}
}
printf("%.2lf",floor(l*100)/100);
return 0;
}题目描述
木材厂有?n?根原木，现在想把这些木头切割成?k?段长度均为?l?的小段木头（木头有可能有剩余）。
当然，我们希望得到的小段木头越长越好，请求出?l?的最大值。
木头长度的单位是?cmcm，原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。
例如有两根原木长度分别为?11?和?21，要求切割成等长的?6段，很明显能切割出来的小段木头长度最长为?5。
输入格式
第一行是两个正整数n,k，分别表示原木的数量，需要得到的小段的数量。
接下来?n?行，每行一个正整数Li?，表示一根原木的长度。
输出格式
仅一行，即?l?的最大值。
如果连?1cm1cm?长的小段都切不出来，输出?0。
输入 #1
3 7
232
124
456
输出 #1
114
说明/提示
数据规模与约定
对于?100%的数据，有 1≤n≤105，1≤k≤108，1≤Li?≤108(i∈[1,n])。
二分答案就是说用?二分?的方法枚举答案，具体请看例子：
我现在在一堆木头中找最长的，我可以用一下方法：
表如下：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[100007];
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int l=0,r=1e8+1,m;
while(l+1<r){
m=(l+r)/2;
int cnt=0;
for(int i=1;i<=n;i++)
cnt+=a[i]/m;
if(cnt>=k){
l=m;
}
else{
r=m;
}
}
cout<<l<<endl;
return 0;
}
链接——书的复制 - 洛谷
而言之，就是：
把m个数分成k组，使每组数的和尽量平均。
那么，我们需要二分的其实是这个“平均”的值，也就是复制时间。
把二分出来的复制时间代到输入数据中，就可以判断这个复制时间是否可行。根据题目要求：
尽可能让前面的人少抄写
emmm这个怎么实现呢？
其实啊，我们这么想：我们面前有一面长长的桌子，桌子上从左到右整整齐齐摆着m本书，有k个可怜的娃要去抄书。要使前面的人少抄写，也就是抄靠右边的书的娃要多抄。那么，就要从抄靠右边的书的娃开始枚举，让他尽量多抄。
#include<bits/stdc++.h>
const int N=505;
using namespace std;
int m,k,p[N],f[N][N],sum[N],maxmin;
void Print(int x)
{
if(!x) return;
for(int i=x;i>=0;i--)
{
if(sum[x]-sum[i-1]>maxmin||i==0)
{
Print(i);
cout<<i+1<<" "<<x<<endl;
break;
}
}
}
int main()
{
cin>>m>>k; memset(f,0x3f,sizeof(f));
for(int i=1;i<=m;i++)
{
cin>>p[i];
sum[i]=sum[i-1]+p[i];
f[i][1]=sum[i];
}
f[1][0]=0;
for(int i=2;i<=k;i++)
for(int j=1;j<=m;j++)
for(int q=1;q<j;q++)
f[j][i]=min(f[j][i],max(f[q][i-1],sum[j]-sum[q]));
maxmin=f[m][k];
Print(m);
return 0;
}如果有人想在洛谷上做题，可以点下方链接：
如果你喜欢或想了解一下其他的算法，可以看看以下这些：
DFS深搜：
最后认识一下，我是爱编程的喷火龙廖，我们有缘再见！