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

· · 题解

这就是三分的板题，博客同步

但我太弱了，写的极其暴力，还用到了函数指针这种玩意（戳这里）

三分的讲解在这里

一开始还没有注意到保留五位小数，，，算的比答案还精确

三分就不细讲了，这篇题解主要的意义就是在于函数指针这个小技巧

当你被自己的实现方法卡住，不妨试试这个，sort的cmp也就是这种方法实现的

让一个函数作为另一个函数的指针

#include<cstdio>
#include<cmath>

const double eps = 1e-6;

double a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p;

double f7(double x){
    return a * pow(x,7) + b * pow(x,6) + c * pow(x,5) + d * pow(x,4) + e * pow(x,3) + f * pow(x,2) + g * pow(x,1) + h;
} 

double f8(double x){
    return a * pow(x,8) + b * pow(x,7) + c * pow(x,6) + d * pow(x,5) + e * pow(x,4) + f * pow(x,3) + g * pow(x,2) + h * pow(x,1) + i;
} 

double f9(double x){
    return a * pow(x,9) + b * pow(x,8) + c * pow(x,7) + d * pow(x,6) + e * pow(x,5) + f * pow(x,4) + g * pow(x,3) + h * pow(x,2) + i * pow(x,1) + j;
} 

double f10(double x){
    return a * pow(x,10) + b * pow(x,9) + c * pow(x,8) + d * pow(x,7) + e * pow(x,6) + f * pow(x,5) + g * pow(x,4) + h * pow(x,3) + i * pow(x,2) + j * pow(x,1) + k;
} 

double f11(double x){
    return a * pow(x,11) + b * pow(x,10) + c * pow(x,9) + d * pow(x,8) + e * pow(x,7) + f * pow(x,6) + g * pow(x,5) + h * pow(x,4) + i * pow(x,3) + j * pow(x,2) + k * pow(x,1) + l;
} 

double f12(double x){
    return a * pow(x,12) + b * pow(x,11) + c * pow(x,10) + d * pow(x,9) + e * pow(x,8) + f * pow(x,7) + g * pow(x,6) + h * pow(x,5) + i * pow(x,4) + j * pow(x,3) + k * pow(x,2) + l * pow(x,1) + m;
} 

double f13(double x){
    return a * pow(x,13) + b * pow(x,12) + c * pow(x,11) + d * pow(x,10) + e * pow(x,9) + f * pow(x,8) + g * pow(x,7) + h * pow(x,6) + i * pow(x,5) + j * pow(x,4) + k * pow(x,3) + l * pow(x,2) + m * pow(x,1) + n;
} 

double trichotomy(double L,double R,double (*f)(double)){
    double mid,mmid;

    while(R - L >= eps){
        mid = L + (R - L) / 3;
        mmid = R - (R - L) / 3;

        if(f(mid) <= f(mmid)){
            L = mid;
        }else{
            R = mmid;
        }
    }

    return (mid + mmid) / 2;
}

int main(){
    a = b = c = d = e = f = g = h = i = j = l = m = n = o = p = 0;

    int cnt;
    scanf("%d",&cnt);
    double L,R;
    scanf("%lf %lf",&L,&R);

    if(cnt == 7){
        scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f,&g,&h);
        printf("%.5lf",trichotomy(L,R,f7));
    }else if(cnt == 8){
        scanf("%lf %lf %lf %lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f,&g,&h,&i);
        printf("%.5lf",trichotomy(L,R,f8));
    }else if(cnt == 9){
        scanf("%lf %lf %lf %lf %lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f,&g,&h,&i,&j);
        printf("%.5lf",trichotomy(L,R,f9));
    }else if(cnt == 10){
        scanf("%lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f,&g,&h,&i,&j,&k);
        printf("%.5lf",trichotomy(L,R,f10));
    }else if(cnt == 11){
        scanf("%lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f,&g,&h,&i,&j,&k,&l);
        printf("%.5lf",trichotomy(L,R,f11));
    }else if(cnt == 12){
        scanf("%lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f,&g,&h,&i,&j,&k,&l,&m);
        printf("%.5lf",trichotomy(L,R,f12));
    }else if(cnt == 13){
        scanf("%lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f,&g,&h,&i,&j,&k,&l,&m,&n);
        printf("%.5lf",trichotomy(L,R,f13));
    }

    return 0;
}