LuoguP3382三分法
sshwy
2019-03-04 14:16:58
# 题解
三分即可
考虑将当前区间$(L,R)$三分为$(L,lm,rm,R)$.
若$lm<rm$,则峰值一定不在$(L,lm)$,所以将$L$赋值为$lm$.
同理,若$lm>rm$,则峰值一定不在$(rm,R)$,所以将$R$赋值为$rm$.
# 代码
```cpp
#include<cstdio>
using namespace std;
int n;
double l,r,a[20];
double f(double x){
double res=0,z=1;
for(int i=0;i<=n;i++){
res+=z*a[i];
z*=x;
}
return res;
}
int main(){
scanf("%d%lf%lf",&n,&l,&r);
for(int i=n;i>=0;i--)scanf("%lf",&a[i]);
double L=l,R=r;
while(R-L>1e-7){
double mid=(R-L)/3;
if(f(L+mid)<f(R-mid))L+=mid;
else R-=mid;
}
printf("%.5lf",L);
return 0;
}
```