HDU - 2899 Strange fuction 二分/三分

2019-11-10 18:59:42

字体：大中小

来源：转载

供稿：网友

Strange fuction

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

这题有两个思路，都需要一点数学一个思路是可以明显看出这个函数在[0,100]上是一个凹函数，那么由此可以使用三分另一个思路是利用最值点导数值为0这一性质，于是我们也可以采用二分我用的是后一种思路，不多说直接上代码吧

代码

#include <cmath>#include <iostream>using namespace std;double y;double f(double x);long double f_p(double x);int main(){ int N; double mid,high,low; cin>>N; while(N--){ cin>>y; high=100,low=0; mid=(low+high)/2; while((fabs(f_p(mid))>1e-4)){ if(f_p(mid)<0){ low=mid; }else{ high=mid; } mid=(low+high)/2; } PRintf("%.4f/n",f(mid)); } return 0;}long double f_p(double x){ long double z=42*pow(x,6)+48*pow(x,5)+21*pow(x,2)+10*x; return (z-y);}double f(double x){ return 6*pow(x,7)+8*pow(x,6)+7*pow(x,3)+5*pow(x,2)-y*x;}

上一篇：LintCode 30：Insert Interval

下一篇：凸优化和非凸优化