题解 P3382 【【模板】三分法】

Seauy · 2019-08-28 12:54:46 · 题解

做的时候样例莫名WA了……

看了半天没看出来，想点开题解看看，然而……

我：“这 ** 居然能用粒子群？还有dalao用了%你退货！？怎么连求导二分都出来了？”

我要的三分呢 QAQ ？

然后 BUG 调好了，看见题解里没有正经的三分写法

那我就义不容辞喽 QAQ

不会三分的话点这：戳

本题代码来了：

#include<bits/stdc++.h>
using namespace std;

const double dif=1e-7;
const int MAXN=13;

int n;
double coe[MAXN+5];

double check(double x)//不用秦九韶公式，普通计算……
{
    double temp=1.0,ans=0.0;
    for(int i=n;i>=0;i--,temp*=x) ans+=coe[i]*temp;
    return ans;
}

double Find(double L,double R)
{
    double Lmid,Rmid;
    while(L+dif<=R)
    {
        Lmid=L+(R-L)/3.0;
        Rmid=R-(R-L)/3.0;
        if(check(Lmid)>check(Rmid)) R=Rmid;
        else L=Lmid;
    }
    return (Lmid+Rmid)/2.0;
}

int main()
{
    double L,R;
    scanf("%d",&n),cin>>L>>R;
    for(int i=0;i<=n;i++) cin>>coe[i];
    printf("%.5lf\n",Find(L,R));
    //printf("%.5lf\n",check(-0.41421));
    return 0;
}