如果想看题目
出门右转
http://wenku.baidu.com/view/6b3f03a6284ac850ad0242fa.html
先吐槽一下
真是后悔啊，说到此题
考场上写出式子死磕1小时无果
决定做前40分，后面的用随机调整
可是，研究半天知道要logn..可是连三分都不会了
囧
后来讲题是说此法有60~100分
常中的投影仪不给力，解题报告也基本没听到啥
正解是二分导数
即拉格朗日乘数法
http://baike.baidu.com/view/1211517.htm
http://zh.wikipedia.org/wiki/拉格朗日乘数
当时在讲题时听到拉格朗日我就已经决定睡觉了
回家休息了
那天复习到函数
有一道用均值不等式求多变量函数极值
我想起这个
一翻书看
后悔了
当时看高数时看完偏导数直接看多重积分去了
中间跳过的，真是拉格朗日乘数
学过导数的话，这个真的很好理解
哭啊
那么接下来将就是
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++)
7using namespace std;
8#define ll long long
9const int maxn=10010;
10int N;
11double E,s[maxn],v[maxn],k[maxn],maxv[maxn],tem[maxn];
12
double solve(double a,double b,double c,double d,double l,double r){
13
double mid;
14
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
}
22void file(){
23 freopen("bicycling.in","r",stdin);
24 freopen("bicycling.out","w",stdout);
25}
26int main()
27{
28 //file();
29 scanf("%d%lf",&N,&E);double low=0;
30 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 {
42 mid=(left+right)/2.0;sum=0.0;
43 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评测
如下图
部分正确是个意外，该点手工测试是正确的
可是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 阅读(3848)
评论(3) 编辑 收藏 引用 所属分类:
programming