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];
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}

#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 阅读(3575) 评论(3)  编辑 收藏 引用 所属分类: programming

FeedBack:
# re: NOI2012 骑行川藏 bicycling
2012-08-13 22:02 | Cheap lace wigs

# re: NOI2012 骑行川藏 bicycling
2012-08-18 16:16 | skyfisherman

# re: NOI2012 骑行川藏 bicycling
2012-08-18 18:59 | prime56
@skyfisherman

 < 2012年8月 >
2930311234
567891011
12131415161718
19202122232425
2627282930311
2345678

•