NOI2012 骑行川藏 bicycling

prime56 — Mon, 13 Aug 2012 11:45:00 GMT

如果想看题目
出门右转
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
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];
12double 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
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
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原创....转载请注明

prime56 2012-08-13 19:45 发表评论

Welcome To My Blog

prime56 — Mon, 13 Aug 2012 05:25:00 GMT

NOI拿块铁牌回家

滚粗了

在WC上也拿张成绩证明的我，在NOI上悲剧了

现在也休息的差不多了

还有300天不到，就要高考了

只有好好加油了

申请新的blog

总之

welcome to my blog

prime56 2012-08-13 13:25 发表评论

C++博客-prime56是蒟蒻

NOI2012 骑行川藏 bicycling

Welcome To My Blog