hdu 2899 Strange fuction （三分）

E - Strange fuction

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

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

感觉一开始完全被唬到了听完凯神说的才知道三分其实和二分没什么本质差别

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;//F(x) = 6 * x^7+8*x^6+7*x^3+5*x^2-y*x (0 <= x <=100)
double pow(double x,int n)
{
    double ans=1.0;
    for(int i=1;i<=n;i++)
    {
        ans*=x;
    }
    return ans;
}
double fun(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 n;
    double x,y;
    double l,r;
    double midl,midr;
    cin>>n;
    while(n--)
    {
        cin>>y;
        l=0.0;r=100.0;
        while(r-l>=0.0000001)// 这里必须足够小 否则误差较大
        {
            midl=l+(r-l)/3;
            midr=l+2*(r-l)/3;

            if(fun(midl,y)<fun(midr,y)) r=midr;
            else l=midl;
        }
        printf("%.4lf
",min(fun(l,y),fun(r,y)));
    }
    return 0;
}