HDU 2899 Strange fuction （三分）

题目

Problem Description
Now, here is a fuction:
F(x) = 6 * x^7+8*x6+7x^3+5*x2-yx (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<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define rep(i,f_start,f_end) for (int i=f_start;i<=f_end;++i)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define MT(x,i) memset(x,i,sizeof(x) )
#define rev(i,start,end) for (int i=start;i<end;i++)
#define inf 0x3f3f3f3f
#define mp(x,y) make_pair(x,y)
#define lowbit(x) (x&-x)
#define exp 1e-8
#define N 1000005 
#define fi first 
#define se second
#define pb push_back
const int mod=1e9+7;
typedef long long ll;
typedef vector <int> VI;
typedef pair<int ,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<int ,PII> PIII;
ll gcd (ll a,ll b) {return b?gcd (b,a%b):a; }
inline int read() {
    char ch=getchar(); int x=0, f=1;
    while(ch<'0'||ch>'9') {
        if(ch=='-') f=-1;
        ch=getchar();
    } while('0'<=ch&&ch<='9') {
        x=x*10+ch-'0';
        ch=getchar();
    } return x*f;
}

int y;


double val(double x){
    return 6*x*x*x*x*x*x*x+8*x*x*x*x*x*x+7*x*x*x+5*x*x-y*x;
}

inline void solve (double l,double r) {
   cin>>y;
   while (l+exp<r) {
       double lmid=l+ (r-l)/3,rmid=l+2*(r-l)/3;
       if (val (lmid)<val(rmid)) {
           r=rmid;
       }
       else l=lmid;
   }
   printf ("%.4f
",val (l));
}

int main () {
    int t;
    cin>>t;
    while (t--) {
        solve (0,100.0);
    }

    return 0;
}