hdu 2899 Strange fuction
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3212 Accepted Submission(s): 2351
Problem Description
Now, here is a fuction:
F(x) = 6 * x^7+8*x^6+7*x^3+5*x^2-y*x (0 <= x <=100)
Can you find the minimum value when x is between 0 and 100.
Input
The first line of the input contains an integer T(1<=T<=100) which means the number of test cases. Then T lines follow, each line has only one real numbers Y.(0 < Y <1e10)
Output
Just the minimum value (accurate up to 4 decimal places),when x is between 0 and 100.
Sample Input
2
100
200
Sample Output
-74.4291
-178.8534
/*题解：
二分法求解，精度1e-7 ，原理简单，不知道最好在纸上比划比划
*/
#include<cstdio>
#include<cmath>
double ys(double x,double y)
{
return 42*pow(x,6)+48*pow(x,5)+21*pow(x,2)+10*x-y;
}
double ans(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()
{
int T;
double y,fx;
scanf("%d",&T);
while(T--)
{
scanf("%lf",&y);
double f1,f2;
f1=0,f2=100;
while(f2-f1>1e-7)
{
fx=(f2+f1)/2;
if(ys(fx,y)>0)
{
f2=fx-1e-9;
}
else
{
f1=fx+1e-9;
}
}
printf("%.4lf\n",ans(fx,y));
}
return 0;
}
/*
三分法可直接求解
定义了L和R，m = (L + R) / 2，mm = (m + R) / 2; 如果m靠近极值点，则R = mm；否则就是mm靠近极值点，则L = m ，和二分法原理基本一样。
*/
#include<cstdio>
#include<cmath>
int y;
double fun(double x)
{
return 6*pow(x,7)+8*pow(x,6)+7*pow(x,3)+5*pow(x,2)-x*y;
}
double search()
{
double L,R,mid,midmid;
L=0,R=100;
while(R-L>1e-6)
{
mid=(L+R)/2;
midmid=(mid+R)/2;
if(fun(mid)<fun(midmid))
R=midmid;
else
L=mid;
}
return L;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&y);
printf("%.4lf\n",fun(search()));
}
}