注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

告别迷茫

梦想与现实的差距,就是我们生活的意义。因为我们有差距,我们才会一直积累,在努力。

 
 
 

日志

 
 

HDU 2899 strange fuction 三分 满足的条件是 有凸包的性质  

2014-04-24 22:39:11|  分类: 搜索的入门 二分 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |


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.
题解:函数是凸性的,用二分搜索需要做特殊处理,求解凸性函数用三分搜索是比较方便的。

类似二分的定义Left和Right,mid = (Left + Right) / 2,midmid = (mid + Right) / 2; 
如果mid靠近极值点,则Right = midmid;否则(即midmid靠近极值点),则Left = mid;

对于求最大极值,if(sum_mid>sum_midmid)
                r=midmid-1e-8;
对于求最小极值 ,if(sum_mid<sum_midmid)
                r=midmid-1e-8;
#include<cstdlib>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LL long long
#define maxn 10001
#define INF 2147483646
using namespace std;
#define eps 1e-7
double mid_pow(double u,double y)
{
    return (6*pow(u,7.0)+8*pow(u,6.0)+7*pow(u,3.0)+5*pow(u,2.0)-y*u);
}
int main()
{
    int T;
    double y,l,r,x,mid,midmid;
    cin>>T;
    while(T--)
    {
        cin>>y;
        l=0,r=100;
        while(r-l>eps)
        {
            mid=(l+r)/2.0;
            midmid=(mid+r)/2.0;
            double sum_mid=mid_pow(mid,y);
            double sum_midmid=mid_pow(midmid,y);
            if(sum_mid<sum_midmid)//求解最小极值
                r=midmid-1e-8;
            else
                l=mid-1e-8;
        }
        printf("%.4lf\n",mid_pow(midmid,y));
    }
}







Strange fuction

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



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 2141 3400 1969 

 


Statistic | Submit | Discuss | Note






Home | TopHangzhou
Dianzi University Online Judge 3.0
Copyright ? 2005-2014 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang
Rongtao
 LinLe GaoJie GanLu
Total
0.003970(s) query 5, Server time : 2014-04-24 22:01:36, Gzip enabled
Administration

#include<stdio.h>
#include<math.h>

double fx(double x,double y)
{
return 6*pow(x,7.0)+8*pow(x,6.0)+7*pow(x,3.0)+5*pow(x,2.0)-y*x;

}
double bottom,top,mid;
int main()
{
double y;
int T;
double liftthird,rightthird;
scanf("%d",&T);
while(T--)
{
scanf("%lf",&y);

bottom=0;
top=100;
while(top-bottom>1e-6)/*两者之间的差即为我们的精度*/
{
liftthird=(2*bottom+top)/3;
rightthird=(bottom+top*2)/3;
if(fx(liftthird,y)<fx(rightthird,y)) /*使用的条件:凸包,2:我们的每次只能把最大的部分舍掉,求最小的值*/
{
top=rightthird-1e-7;/*求解最大的值得时候只能舍掉最小的部分吧 ,证明见PPT*/
}
else
{
bottom=liftthird-1e-7;
}
//printf("%.4lf %.4lf",top ,bottom);


}
printf("%.4lf\n",fx((bottom+top)/2,y));

}
return 0;
}



  评论这张
 
阅读(5)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017