P3382&HDU-2899(三分模板+秦九韶算法)

题目

输入：
3 -0.9981 0.5
1 -3 -3 1

输出：
-0.41421

时空限制：50ms,128M
数据规模：7<=N<=13

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#define m(a,b) memset(a,b,sizeof a)
#define en '\n'
#define eps 1e-6
using namespace std;
typedef double du;
const int N=13+2;
du coef[N];int n;
du work(du x)//秦九韶算法
{
    du res=coef[1];
    for(int i=2;i<=n+1;i++)
        res=res*x+coef[i];
    return res;
}
int main()
{
    du l,r;scanf("%d%lf%lf",&n,&l,&r);
    for(int i=1;i<=n+1;i++)
        scanf("%lf",&coef[i]);
    du m1,m2;
    while(fabs(r-l)>eps)
    {
        m1=l+(r-l)/3.0,m2=r-(r-l)/3.0;
        if(work(m1)>work(m2))
            r=m2;
        else
            l=m1;
    }
    printf("%.5f\n",l);
}

题目

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#define m(a,b) memset(a,b,sizeof a)
#define en '\n'
#define eps 1e-6
using namespace std;
typedef double du;
typedef long long ll;
const int INF=0x3f3f3f3f,N=13+2;
du coef[9]={6,8,0,0,7,5,0,0};
du y;
du work(du x)
{
    coef[6]=-y;
    du res=coef[0];
    for(int i=1;i<=7;i++)
        res=res*x+coef[i];
    return res;
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        scanf("%lf",&y);
        du l=0.0,r=100.0,m1,m2,ans;
        while(r-l>eps)
        {
            m1=(l+r)/2,m2=(m1+r)/2;
            if(work(m1)>(ans=work(m2)))
                l=m1;
            else
                r=m2;
        }
        printf("%.4f\n",ans);
    }
}