题目
将函数进行求导,根据得到的导数可判断其导数的单调性为单调递增。当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;
}