2021-06-24

题目
将函数进行求导，根据得到的导数可判断其导数的单调性为单调递增。当F’(x)=0时，可得到min(F(x))。此时可利用二分查找（binary search）。
利用三分查找之前，可判断凸包的位置，求导是其中的一个方法。之前刷CF时，看到有人用三分查找（ternary search），今天第一次接触和学习这个算法。也对二分查找有了新的认识。

#include <cstdio>
#include <cmath>
#define T int T; scanf("%d", &T); while(T--)
double f(double x){
	return 42*pow(x, 6)+48*pow(x, 5)+21*pow(x, 2)+10*x;
}

double F(double x, double y){
	return 6*pow(x, 7)+8*pow(x, 6)+7*pow(x, 3)+5*pow(x, 2)-y*x;
}

int main()
{
    T{//二分查找
    	double y;
    	scanf("%lf", &y);
    	double left=0, right=100;
    	while(right-left>=1e-6){
    		double mid=(right+left)/2;
    		if(f(mid)<y)
    			left=mid+1e-7;
    		else if(f(mid)>y)
    			right=mid-1e-7;
    	}

        printf("%.4f %.4f\n", left, right);
    	printf("%.4f\n", F((left+right)/2, y));
    }
	return 0;
}

#include <cstdio>
#include <cmath>
#define T int T; scanf("%d", &T); while(T--)
double f(double x, double y){
	return 6*pow(x, 7)+8*pow(x, 6)+7*pow(x, 3)+5*pow(x, 2)-y*x;
}

int main()
{
    T{//三分查找
    	double y;
    	scanf("%lf", &y);
    	double left=0, right=100;
    	while(right-left>=1e-6){
    		double leftside=(2*left+right)/3;
    		double rightside=(left+2*right)/3;
    		if(f(leftside, y)<f(rightside, y)){
    			right=rightside;
    		} else if(f(leftside, y)>f(rightside, y)){
    			left=leftside;
    		}
    	}
        
    	printf("%.4f\n", f((left+right)/2, y));
    }
	return 0;
}