本篇主要介绍二分答案的几个模板
1.常用二分模板
整数二分模板1
-
将区间划分为[l,mid]和[mid+1,r]
-
则对应的边界更新操作为r=mid,和l=mid+1;
-
中点mid不要+1(相当于向下取整);
//整数二分模板1
int bsearch_1(int l,int r)
{
while(l < r)
{
mid = (l+r)>>1;
if(check(mid)) r = mid;
else l = mid+1;
}
return l;
}
整数二分模板2
-
将区间划分为[l,mid-1]和[mid,r]
-
则对应的边界更新操作为r=mid-1,和l=mid;
-
中点mid要+1(相当于向上取整);
//整数二分模板2
int bsearch_2(int l,int r)
{
while(l < r)
{
mid = (l+r+1)>>1;
if(check(mid)) r = mid-1;
else l = mid;
}
return l;
}
实数二分模板1
-
因为对实数而言，任意两个数中间都有无数个点存在，因此实数的二分都会有精度要求
所以对于题目所给精度k，一般二分时的精度esp = 1e-(k+2);
例如保留4位小数，则esp设置为1e-6;
-
因此实数二分查找的一般都是某个区间,对于一些点需要进行特殊的判定
-
然后关于左右区间的判定都与所写的check函数的条件有关
double bsearch_d1(double l,double r)
{
double esp = 1e-6;//1e -(k+2),k为保留k位小数
mid = (l+r)*0.5;//或mid = (l+r)/2;此时注意不能使用位运算
while(r-l > esp)
{
if(check(mid)) r = mid;//去掉右区间
else l = mid;//去掉左区间
}
return l;
}
实数二分模板2
-
基于实数的二分迭代无法进行彻底，只能将所求值在某个精度要求下近似
-
因此可以用近似迭代降低一部分精度，节省出一部分运行时间
-
根据某up主关于yxc的二分总结，迭代100次左右，结果基本稳定；代码如下：
double bsearch_d1(double l,double r)
{
double esp = 1e-6;//1e -(k+2),k为保留k位小数
for(int i = 1;i <= 100;i++)
{
double mid = (l+r)*0.5;
if(check(mid)) r = mid;//去掉右区间
else l = mid;//去掉左区间
}
return l;
}
eg1 洛谷P1024 [NOIP2001 提高组] 一元三次方程求解
[NOIP2001 提高组] 一元三次方程求解
题目描述
有形如：$a x^3 + b x^2 + c x + d = 0$ 这样的一个一元三次方程。给出该方程中各项的系数（$a,b,c,d$ 均为实数），并约定该方程存在三个不同实根（根的范围在 $-100$ 至 $100$ 之间），且根与根之差的绝对值 $\ge 1$。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 $2$ 位。
提示：记方程 $f(x) = 0$，若存在 $2$ 个数 $x_1$ 和 $x_2$，且 $x_1 < x_2$，$f(x_1) \times f(x_2) < 0$，则在 $(x_1, x_2)$ 之间一定有一个根。
输入格式
一行，$4$ 个实数 $a, b, c, d$。
输出格式
一行，$3$ 个实根，从小到大输出，并精确到小数点后 $2$ 位。
样例 #1
样例输入 #1
1 -5 -4 20
样例输出 #1
-2.00 2.00 5.00
提示
【题目来源】
NOIP 2001 提高组第一题
ac代码：
#include<bits/stdc++.h>
#define N 1005
#define mod 998244353
#define float double
using namespace std;
typedef long long ll;
double a,b,c,d;
float check(float m)
{
float num = a*m*m*m+b*m*m+c*m+d;
return num ;
}
void solve()
{
cin>>a>>b>>c>>d;
float x,ans;
for(float i = -100;i <= 100;i++)//因为题目规定了答案区间，所以只需要在[-100,100]之间进行遍历
{
float l = i;
float r = l+1;
if(check(i)==0) cout<<fixed<<setprecision(2)<<i<<" ";//这里进行特殊判断就是上文中提到的对于实数二分只能确定某个区间然后从两侧近似，若区间 值恰好相等则进行特判
else
{
if(check(l) * check(r) < 0)
{
while((r-l) > 1e-4)//注意精度 esp = 1e -(k+2);
{
float mid = (l+r)/2;
if(check(l) * check(mid) <= 0) r = mid;
else l = mid;
}
cout<<fixed<<setprecision(2)<<l<<" ";//不使用printf的控制小数位数的方法
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
solve();
return 0;
}