HDU 2899 Strange fuction

原题传送门：http://acm.hdu.edu.cn/showproblem.php?pid=2899

 

 

Strange fuction

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3021    Accepted Submission(s): 2235

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

 

 

Author

 

Redow

 

 

Recommend

 

lcy   |   We have carefully selected several similar problems for you:  2289 2298 3400 1969 1551

 

分析：首先分析这个函数单调性，对其求导得到42*x^6+48*x^5+21*x^2+10*x-y;很明显原函数0-100内先减后增大，那么一定存在一个x0,使得原函数最小，那么x0怎么求？

我们可以用一阶导数==0的时候，求得x0,问题就化为，用二分法求方程42*x^6+48*x^5+21*x^2+10*x-y = 0；时候的x0的值了，具体求法详见博客http://hellojyj.iteye.com/blog/2093672

//二分法求方程最值 HDU 2899
#include<cstdio>
#include<cmath>
double low,mid,high;
int Y,t;
using namespace std;
double ff(double x,int y){
    double result = 42*pow(x,6)+48*pow(x,5)+21*pow(x,2)+10*x-y;
    return result;
}
double f(double x,int y){
    double result = 6*pow(x,7)+8*pow(x,6)+7*pow(x,3)+5*pow(x,2)-y*x;
    return result;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&Y);
        low = 0.0;
        high = 100.0;

        while(low<high)
        {
            mid = (low+high)/2;
            if(fabs(ff(mid,Y))<= 0.000001)
            {
                break;
            }else if(ff(mid,Y)>0)
            {
                high = mid;
            }else
            {
                low = mid;
            }
        }

        printf("%.4f\n",f(mid,Y));
    }
}