篇首语
啊~~三分~你比二分多一分~
——A86562U
正文
顾名思义,三分会比二分多一个分区,
但它是用来做什么的呢?
先来偷一道拿一道例题来举例
P3382 三分 - 洛谷
我们把二分的模板偷一份拿一份过来
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e1+10;
int n;
double l,r,a[N];
double check(double x)
{//求多项式,复制的 double sum=0;for(int i=n;i>=0;i--){sum=sum*x+a[i];}return sum;
}
signed main()
{cin>>n>>l>>r;for(int i=n;i>=0;i--)//反向输入系数
{cin>>a[i];}while(fabs(l-r)>=eps){double mid=(l+r)/2;if(check(mid)</*???*/){l=mid;//舍弃左区间
}else{r=mid;//舍弃右区间
}}printf("%.6f",r);return 0;
}
可是我们需要比较两次(l与中间值比较,r与中间值比较),而我们甚至不知道中间值是不是对的。所以我们要使用神奇的妙妙工具(1):
eps
eps是步长,一般是指定的精度的十分之一。它可以让我们的代码变成这样:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e1+10;
const double eps=1e-6;
int n;
double l,r,a[N];
double check(double x)
{//求多项式,复制的 double sum=0;for(int i=n;i>=0;i--){sum=sum*x+a[i];}return sum;
}
signed main()
{cin>>n>>l>>r;for(int i=n;i>=0;i--)//反向输入系数
{cin>>a[i];}while(fabs(l-r)>=eps)//l<=r可能会发生精度问题
{double mid=(l+r)/2;if(check(mid+eps)>check(mid-eps)){l=mid;//舍弃左区间
}else{r=mid;//舍弃右区间
}}printf("%.6f",r);return 0;
}
这样可以把mid左边一点点的函数值和右边一点点的函数值比较,舍弃一边的区间,这样不断缩小区间直到满足精度要求。
这,就是三分。