题解【算法1-6】二分查找与二分答案

T1 P2249 【深基13.例1】查找

二分查找的板子

二分查找需要定义三个变量， $l$ (序列的左端)， $r$ (序列的右端)和 $mid$ (中间点)。二分查找的前提是序列有序（一般是升序排列）。

二分查找的原理为：如果中间数小于查找数，那么位置一定在中间数的右边，反之左边。当序列长度为1时停止查找。

以下是程序的板子，最后输出 $l$ 即可。

while(l<r)
{
		mid=(l+r)/2; //防溢出的话也可以写成l+(r-l)/2
		if(a[mid]>=x) r=mid;
		else l=mid+1;
}

当然如果你懒得打 $mid+1$ 的话，也可以写本人比较喜欢的板子

l=1;r=n+1; //注意这里和下面的的+1
while(l+1<r) 
{
		mid=(l+r)/2;
		if(a[mid]>=x) r=mid;
		else l=mid;
}

然而这个板子的答案有时候会玄学的出现在 $l,l-1,l+1$ 中的一个，所以需要特判。如果这三个答案都不等于查找数，那就是找不到。

该算法单次查询时间复杂度为 $O(\log n)$ ，可以通过本题。

AC Code ：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000010],x,mid,l,r;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);//因为题目里已经说了有序，就不用再排序了。
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&x);
		l=1;r=n+1;
		while(l+1<r)
		{
			mid=(l+r)/2;
			if(a[mid]>=x) r=mid;
			else l=mid;
		}
		if(a[l]==x) printf("%d ",l);
		else if(a[l+1]==x) printf("%d ",l+1);
		else printf("-1 ");
	}
	return 0;
}

T2 P1102 A-B 数对

~~二分题单？我就不用二分~~

~~其实是这个菜鸡不会写二分~~

对于这道题，我们只需要把等式变成 $A=B+C$ ，然后用一个 map 记录 $a_i$ 出现的次数。然后将每个 $a_i+c$ 的出现次数累加即可。

因为这题比较简单，所以只要把 map 当普通数组用就行了~~本来就是这样~~

当然二分也可以，枚举 $b$ ，二分查找满足的 $c$ 即可。

AC Code ：

#include<bits/stdc++.h>
using namespace std;
int n;
long long x,a[2000010],s; //要注意的是longlong
map<long long,long long> b;
int main()
{
	cin>>n>>x;
	for(int i=1;i<=n;i++) 
	{
		scanf("%lld",&a[i]);
		b[a[i]]++;
	}
	for(int i=1;i<=n;i++) s+=b[a[i]+x];
	cout<<s;
	return 0;
}

T3 P1873 砍树

二分算法分为两种，二分查找和二分答案。

本题就是二分答案的板子。

二分答案的原理是，在一个范围内查找符合题意的最大的答案。（也有可能不是最大）。别的和二分查找基本相同。

和二分查找不同的是，二分答案的范围不是从 $1$ 到 $n$ ，同时二分答案多了一个用来检查 $mid$ 是否合法的 check 函数（也可以写在二分 while 循环内）

二分答案的板子

sort(a+1,a+n+1);
l=1;r=最大的范围（一般为max{a[i]}+1);
while(l+1<r)
{
	mid=(l+r)/2;
	if(check(mid)) l=mid;
	else r=mid;
}
cout<<l;
        
int check(int x)
{
	定义
	for(int i=1;i<=n;i++)
	  do something.....
	return 合法条件
}

对于本题，首先确定查找范围 $1$ 到 $\max{a_i}+1 $。

~~LaTeX不会写~~

然后就是 check 函数，只要求出 $\sum_{i=1}^N a_k-mid$ ，然后把它和 $m$ 比较就行了。

时间复杂度为 $O(n \log n)$ ，可以通过本题。

AC Code :

#include<bits/stdc++.h>
using namespace std;
int n;
long long l,r,mx,a[1000010],m,mid;
int check(int x)
{
	long long s=0;
	for(int i=1;i<=n;i++)
	  if(a[i]>x) s+=(a[i]-x);
	if(s>=m) return 1;
	return 0;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) {scanf("%lld",&a[i]);mx=max(mx,a[i]);}
	sort(a+1,a+n+1);
	l=1;r=mx+1;
	while(l+1<r)
	{
		mid=(l+r)/2;
		if(check(mid)) l=mid;
		else r=mid;
	}
	cout<<l;
	return 0;
}

T4 P1024 [NOIP2001 提高组] 一元三次方程求解

~~这[数据删除]是二分？~~

本题暴力即可。这题掉红的原因就是因为可以暴力。

AC Code ：

#include<bits/stdc++.h>
using namespace std;
double a,b,c,d;
int main()
{
   cin>>a>>b>>c>>d;
   for(double i=-100;i<=100;i+=0.001)
   {
      double j=i+0.001;
      double x=a*i*i*i+b*i*i+c*i+d;
      double y=a*j*j*j+b*j*j+c*j+d;
      if(x>=0&&y<=0||x<=0&&y>=0)
         printf("%.2lf ",i);
   }
   return 0;
}

~~诶那你倒是写个二分啊？~~

~~懒的写~~

T5 P1678 烦恼的高考志愿

因为要相差最小，所以用二分查找到最接近 $b_i$ 且小于其的 $a_l$ ,然后取 $|a_lk-b_i|,|a^{l-1}-b_i|,|a^{l+1}-b_i|$ 的最小值即可。

同时当 $b_i<a_1$ 或 $b_i>a_n$ 时特判。

AC code ：

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long a[100100],b[100100],s,l,r,mid;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=m;i++) scanf("%d",&b[i]);
	sort(a+1,a+n+1);
	for(int i=1;i<=m;i++)
	{
		l=1;r=n+1;
		while(l+1<r)
		{
			mid=(l+r)/2;
			if(a[mid]<b[i]) l=mid;
			else r=mid;
		}
		if(b[i]<a[1]) s+=abs(a[1]-b[i]);
		else if(b[i]>a[n]) s+=abs(b[i]-a[n]);
		else s+=min(min(abs(a[l+1]-b[i]),abs(a[l-1]-b[i])),abs(a[l]-b[i]));
	}
	cout<<s;
	return 0;
}

T6 P2440 木材加工

二分答案的板子。

对于这道题，需要二分答案的就是题目所求的最大值。如果长度为 $mid$ 那么第 $i$ 个木条就会被切割成 $\left\lfloor\dfrac{a_i}{mid}\right\rfloor$ 断，因此求出 $\sum_{i=1}^N \left\lfloor\dfrac{a_i}{mid}\right\rfloor$ 的值，和 $m$ 进行比较，就是 check 函数了。

因为最大的一段不肯能超过 $\max{a_i}$ ,所以把 $r$ 的初始值定为 $\max{a_i}+1$ 。

对于 $0$ 的情况，因为切 $1$ 厘米的小段就是段数最多的情况，所以将读入的 $a$ 数组求和，如果和小于 $m$ ，则就是切不出来。

AC Code ：

#include<bits/stdc++.h>
using namespace std;
int n,l,r,mid;
long long a[100010],mx,m,sum;
int check(int x)
{
	long long s=0;
	for(int i=1;i<=n;i++) s+=a[i]/x;
	if(s>=m) return 1;
	return 0;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) {scanf("%lld",&a[i]);mx=max(mx,a[i]);sum+=a[i];}
	if(sum<m) {cout<<0;return 0;}
	l=1;r=mx+1;
	while(l+1<r)
	{
		mid=(l+r)/2;
		if(check(mid)) l=mid;
		else r=mid;
	}
	cout<<l;
	return 0;
}

T7 P2678 [NOIP2015 提高组] 跳石头

~~不错，长得真像二分。~~

~~本来就是二分~~

Part 1 预处理

~~弄得这么高大上干嘛~~

题目给你的只是中间的距离，还需要处理终点，所以 $a_{n+1}=l$

然后确定搜索范围，本题需要二分答案的依然是题目所求的，所以 $left=1$ ， $right=l+1$ 。

Part 2 check 函数

$t$ 表示共移走的石头， $k$ 表示不需要移走的石头的下标。

那么，当 $a_i$ 和 $a_k$ 的距离小于待验证距离 $mid$ 时，就需要移走一块石头，因为题目要求的是最大值，所以两块距离大于等于 $mid$ 的石头之间不应该再有多余的石头。

AC code :

#include<bits/stdc++.h>
#define inf 2147483647
using namespace std;
int n,m;
long long l,r,mid,d,a[123333];
int check(long long x)
{
	long long k=0,t=0;
	for(int i=1;i<=n+1;i++)
	  if(a[i]-a[k]<x)  t++;
	  else k=i;
	return t<=m;
}
int main()
{
	cin>>d>>n>>m;
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	a[n+1]=d;
	sort(a+1,a+n+2);
	l=0;r=d+1;
	while(l+1<r)
	{
		mid=(l+r)/2;
		if(check(mid)) l=mid;
		else r=mid;
	}
	cout<<l;
	return 0;
}

T8 P3853 [TJOI2007]路标设置

没什么可说的了~~你还想说什么~~，直接写 check 函数。

设待验证的空旷指数为 $x$ ，那么当有 $a_i-a_{i-1} > x$ 时，就需要添加路牌。
需要注意的是，当 $a_i-a_{i-1}$ 能被 $x$ 整除时，其中一端的路牌就不用加了。

用代码写出来是这样的

//ans表示一共添加的路牌数量
if((a[i]-a[i-1])%x==0) ans+=(a[i]-a[i-1])/x-1;
	else ans+=(a[i]-a[i-1])/x;

最后把 $ans$ 和 $k$ 比较即可。

还有一个坑点，这题的答案是求最小值，而前面的题目是最大值，所以需要把二分判断中的 if(check(mid)) 改成 if(!check(mid)) 。

AC Code ：

#include<bits/stdc++.h>
using namespace std;
int p,n,m,l,r,mid,a[233333];
int check(int x)
{
	int ans=0;
	for(int i=2;i<=n;i++)
		if(a[i]-a[i-1]>=x) 
		{
			if((a[i]-a[i-1])%x==0) ans+=(a[i]-a[i-1])/x-1;
			else ans+=(a[i]-a[i-1])/x;
		}
	return ans<=m;
}
int main()
{
	cin>>p>>n>>m;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	l=1;r=p+1;
	while(l+1<r)
	{
		mid=(l+r)/2;
		if(!check(mid)) l=mid;
		else r=mid;
	}
	cout<<l+1;
	return 0;
}

T9 P1182 数列分段 Section II

~~菜到先用爆搜写了 1h ，再用区间 dp 写了 1h 。。。。~~

最后发现这题二分的依然是答案（（（（（

主程序依旧是板子，二分题目的颜色估计就是 check 函数决定吧。。。

唯一注意的就是 $l$ 需要定义成 $a_i$ 中的最大值， $r$ 需要定义成所有 $a_i$ 的和。分别表示切 $n-1$ 段和切 $1$ 。

定义 $s$ 表示每段之和, $t$ 表示分的段数，待验证的答案为 $x$ 。则当 $s+a_i > x $ 时，就需要重新分一段，同时将 $i-1$ 作为新一段的起点。

最后将 $t$ 和 $m$ 比较即可。

AC code ：

#include<bits/stdc++.h>
using namespace std;
int n,m,l,r,mid,sum,a[233333];
int check(int x)
{
	int s=0,t=0;
	for(int i=1;i<=n;i++)
	  if(s+a[i]<=x) s+=a[i];
	  else {s=a[i];t++;}
	return t>=m;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) 
	{
		scanf("%d",&a[i]);
		r+=a[i];
		l=max(l,a[i]);
	}
	while(l<=r)
	{
		mid=(l+r)/2;
		if(check(mid)) l=mid+1;
		else r=mid-1;
	}
	cout<<l;
	return 0;
}

最后说一下吧，这种类似于贪心的策略是错误的，题目中给出的例子很明显的 hack 了这个代码，它似乎只会把 $4$ 和 $2$ 放一段，而不会把 $4$ 单独放。本来这个代码只有 $20$ 分，但是将我自己的板子换成传统的二分板子之后就 AC 了，可能是数据的问题。

在第一篇题解下面的评论区中确实有人提出过，但是没有被重视。所以我希望大佬们可以解答一下我的疑惑。

这题正确的方法应该是前缀和二分，但我自己的板子再次被卡掉了，如果 $l+1$ 输出就有 $80$ 但是第四个点恰好不需要加一。

这就是这道题比较麻烦的地方。

T10 P1163 银行贷款

~~这是二分 ?~~

~~我记得当时调了三个小时没 A 气得直接把讨论区求助代码调对了结果自己还是没 A~~

Part 1 确定搜索范围

反正二分的基本就是答案，所以就直接套板子。

利率的左端 $l$ 就是 $0$ ，而右端就需要一些~~动画知识~~。一般来说高利贷的利率不会超过 $10$ 抢钱所以把 $r$ 定义为 $10.0$ 。

因为误差不需要超过 $0.1\%$ ，把 while 里的条件写为 $r-l>0.0001$ （精度）

注意的是 $l$ ， $r$ ， $mid$ ，全部要定义为 double 。

ps ：最后输出的时候一定要乘 $100$ ,题目求的是百分数.

Part 2 check 函数

比较方便的就是计算在这个利率下是否能刚好还玩（多还亿一点点也可以）

设 $t$ 为剩余的钱， $x$ 为待验证的利率，计算利率的时候简便的方法就是把 $t$ 每次增大 $x$ 倍，再减去每个月还的钱。

AC code :

#include<bits/stdc++.h>
using namespace std;
double p,l,r,mid;
int n,m;
int check(double x)
{
	double t=p; //刚开始剩余的钱数就是贷款原值
	for(int i=1;i<=m;i++) t=(1.0+x)*1.0*t-1.0*n;
	return t<=0;
}
int main()
{
	cin>>p>>n>>m;
	l=0.0;r=10.0; 
	while(r-l>0.0001)
	{
		mid=(l+r)/2.0;
		if(check(mid)) l=mid;
		else r=mid;
	}
	printf("%.1lf",1.0*l*100.0); //百分数！
	return 0;
}

T11 P3743 kotori的设备

~~蓝题？玩你m~~

Part 1 无限使用

很简单，只要所有设备一秒内消耗的能量小于等于充电宝一秒内能提供的能量，就意味着能够一直充电。

Part 2 主程序

既然所有和的最大值是 $10^{10}$ 那么就把右边界定义为 $10^{10}$ 。

然后，题目要求的精度是 $10^{-4}$ ，所以当 $r$ 和 $l$ 相差小于等于 $10^{-4}$ 时结束 while 循环。

这样看似范围很大，但是二分的时间复杂度是 $O(\log n)$ ，即使是大数据也就几十而已。

Part 3 check 函数

设待验证的时间为 $x$ 则充电宝最多可以提供 $x*p$ 的能量。设 $t$ 表示在时间 $x$ 内所需充电宝能量，则如果一个设备在 $x$ 秒内消耗的能量小于原来储存的能量，就不需要使用充电宝。

反之，如果要使用充电宝，那么充电宝消耗的能量就是这个设备在 $x$ 秒内消耗的能量减去原储存能量。用 $t$ 做一个累加即可。

最后如果 $t$ 小于等于 $p$ ，就意味着这个时间是合法的。

AC code ：

#include<bits/stdc++.h>
using namespace std;
struct aksres
{
	double x,y;
}a[233333];
int n;
double p,sum,l,r,mid;
int check(double x)
{
	double s=x*p,t=0;
	for(int i=1;i<=n;i++) t+=max(0,x*a[i].x-a[i].y);
	return t<=s;
}
int main()
{
	cin>>n>>p;
	for(int i=1;i<=n;i++)
	{
		scanf("%lf%lf",&a[i].x,&a[i].y);
		sum+=a[i].x;
	}
	if(sum<=p) {cout<<"-1";return 0;}
	l=0.0;r=1e10;
	while(r-l>0.0001)
	{
		mid=(l+r)/2.0;
		if(check(mid)) l=mid;
		else r=mid;
	}
	printf("%.6lf",l);
	return 0;
}

Aksres's Blog