如果想看题目
出门右转
http://wenku.baidu.com/view/6b3f03a6284ac850ad0242fa.html
先吐槽一下
真是后悔啊,说到此题
考场上写出式子死磕1小时无果
决定做前40分,后面的用随机调整
可是,研究半天知道要logn..可是连三分都不会了
囧
后来讲题是说此法有60~100分
常中的投影仪不给力,解题报告也基本没听到啥
正解是二分导数
即拉格朗日乘数法
http://baike.baidu.com/view/1211517.htm
http://zh.wikipedia.org/wiki/拉格朗日乘数
当时在讲题时听到拉格朗日我就已经决定睡觉了
回家休息了
那天复习到函数
有一道用均值不等式求多变量函数极值
我想起这个
一翻书看
后悔了
当时看高数时看完偏导数直接看多重积分去了
中间跳过的,真是拉格朗日乘数
学过导数的话,这个真的很好理解
哭啊
![](/images/cppblog_com/prime56/p2.jpg)
那么接下来将就是
1
#include<stdio.h>
2
#include<iostream>
3
#include<algorithm>
4
#include<cmath>
5
#include<cstdio>
6
#define rep(i,n) for(int i=0;i<n;i++)
7
using namespace std;
8
#define ll long long
9
const int maxn=10010;
10
int N;
11
double E,s[maxn],v[maxn],k[maxn],maxv[maxn],tem[maxn];
12![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
double solve(double a,double b,double c,double d,double l,double r){
13
double mid;
14![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(l+0.000000000001<r){
15
mid=(l+r)/2.0;
16
double ans=a*mid*mid*mid+b*mid*mid+d;
17
if (ans>0.0)l=mid;
18
else r=mid;
19
}
20
return (l+r)/2.0;
21
}
22![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
void file(){
23
freopen("bicycling.in","r",stdin);
24
freopen("bicycling.out","w",stdout);
25
}
26
int main()
27
{
28
//file();
29
scanf("%d%lf",&N,&E);double low=0;
30![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
rep(i,N){
31
double t;
32
scanf("%lf%lf%lf",&s[i],&k[i],&v[i]);
33
if (s[i]>0)
34
maxv[i]=sqrt(E/(k[i]*s[i]))+v[i],t=-(1.0/(2*k[i]*maxv[i]*maxv[i]*(maxv[i]-v[i])));
35
else maxv[i]=s[i];
36
low=min(low,t);
37
}
38
//rep(i,N)printf("maxv %.8lf\n",maxv[i]);
39
double left=-1000,right=low,mid,sum;
40
rep(zz,60)
41![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
42
mid=(left+right)/2.0;sum=0.0;
43![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
rep(i,N){
44
double a=2.0*k[i]*mid;
45
tem[i]=solve(a,-a*v[i],0,1.0,max(v[i],0.000001),maxv[i]);
46
sum+=k[i]*s[i]*(tem[i]-v[i])*(tem[i]-v[i]);
47
}
48
if (sum>E)right=mid;
49
else left=mid;
50
//printf("\n ## %.10lf\n",sum);
51
}
52
long double ret;
53
ret=0.0;
54
rep(i,N)ret+=(long double)s[i]/(long double)tem[i]; printf("%.10lf\n",(double)ret);
55
return 0;
56
}
程序
如上
经过cena评测
如下图
![](/images/cppblog_com/prime56/捕获1.JPG)
部分正确是个意外,该点手工测试是正确的
可是2.29s
这和牛顿迭代怎么比
常数优化来了
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
#define ll long long
const int maxn=10010;
int N;
double E,s[maxn],v[maxn],k[maxn],maxv[maxn],tem[maxn],minv[maxn];
double solve(double a,double b,double c,double d,double l,double r){
double mid;
while(l+0.0000001<r){
mid=(l+r)/2.0;
//printf("%.10lf %.10lf\n",l,r);
double ans=a*mid*mid*mid+b*mid*mid+d;
if (ans>0.0)l=mid;
else r=mid;
}
return (l+r)/2.0;
}
void file(){
freopen("bicycling.in","r",stdin);
freopen("bicycling.out","w",stdout);
}
int main()
{
//file();
scanf("%d%lf",&N,&E);double low=0;
rep(i,N){
double t=0;
scanf("%lf%lf%lf",&s[i],&k[i],&v[i]);
if (s[i]>0)
maxv[i]=sqrt(E/(k[i]*s[i]))+v[i],t=-(1.0/(2*k[i]*maxv[i]*maxv[i]*(maxv[i]-v[i])));
else maxv[i]=v[i];
minv[i]=max(0.000001,v[i]);
low=min(low,t);
}
double left=-1,right=low,mid,sum;
rep(zz,80)
{
mid=(left+right)/2.0;sum=0.0;// 请不要用 while(left+0.0000000001<right) 那个的精度连样例都过不了
rep(i,N){
double a=2.0*k[i]*mid;
tem[i]=solve(a,-a*v[i],0,1.0,minv[i],maxv[i]);
sum+=k[i]*s[i]*(tem[i]-v[i])*(tem[i]-v[i]);//printf(" $$ %.10lf\n",sum);
}
//rep(i,N)printf("%.6lf ",tem[i]);
if (sum>E){
right=mid;
rep(i,N)maxv[i]=tem[i];
}
else{
left=mid;
rep(i,N)minv[i]=tem[i];
}
if (fabs(sum-E)<0.00000001)break;
//printf("\n ## %.10lf\n",sum);
//printf("%.10lf\n",(double)clock()/CLOCKS_PER_SEC);
}
long double ret;
ret=0.0;
//printf("\n");
rep(i,N)if (s[i]>0)ret+=(long double)s[i]/(long double)tem[i];
printf("%.10lf\n",(double)ret);
return 0;
}
时间如下:
时间快了很多
当然,你也可以写牛顿迭代
这道题
据说此题与某省选题巨像,我记不起来了
路过的各位有知道的麻烦给我说一下,谢谢
prime56原创....转载请注明
posted on 2012-08-13 19:45
prime56 阅读(3836)
评论(3) 编辑 收藏 引用 所属分类:
programming