首页 > 代码库 > hdu 2899 凸性 二分 / 三分
hdu 2899 凸性 二分 / 三分
Strange fuction
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7230 Accepted Submission(s): 4996
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.
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
二分先决条件是满足单调性,这里显然不满足不能直接二分,这道题目求导就可以解决,求出极值点,如果求导不方便的题目就得用三分搜索了。
1 #include<iostream> 2 #include<stdio.h> 3 #include<math.h> 4 #define exp 1e-8 5 6 using namespace std; 7 8 double y; 9 10 double suan(double x) 11 { 12 return 42*pow(x,6)+48*pow(x,5)+21*x*x+10*x-y; 13 } 14 double binary(double low,double high) 15 { 16 while(high-low>exp) 17 { 18 double mid = (low+high)/2; 19 if(suan(mid)>0) 20 high=mid-exp; 21 else 22 low=mid+exp; 23 } 24 return low; 25 } 26 int main() 27 { 28 int t; 29 scanf("%d",&t); 30 while(t--) 31 { 32 scanf("%lf",&y); 33 double ans = binary(0,100); 34 printf("%.4f\n",6*pow(ans,7)+8*pow(ans,6)+7*pow(ans,3)+5*ans*ans-y*ans); 35 } 36 return 0; 37 }
三分查找
1 #include<iostream> 2 #include<stdio.h> 3 #include<math.h> 4 #define exp 1e-8 5 6 using namespace std; 7 8 double y; 9 10 double suan(double x) 11 { 12 return 6*pow(x,7)+8*pow(x,6)+7*pow(x,3)+5*x*x-y*x; 13 } 14 double binary(double low,double high) 15 { 16 double mid,mmid; 17 while(high-low>exp) 18 { 19 mid = (low+high)/2; 20 mmid = (high+mid)/2; 21 if(suan(mid)>suan(mmid)) 22 low=mid+exp; 23 else 24 high=mmid-exp; 25 } 26 return (mid+mmid)/2; 27 } 28 int main() 29 { 30 int t; 31 scanf("%d",&t); 32 while(t--) 33 { 34 scanf("%lf",&y); 35 double ans = binary(0,100); 36 printf("%.4f\n",suan(ans)); 37 } 38 return 0; 39 }
hdu 2899 凸性 二分 / 三分
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。