洛谷2179 [noi2012]骑行川藏

拉格朗日乘法入门题

Posted by yjjr's blog on April 3, 2018

标签:拉格朗日乘数法,二分

题目

题目传送门

题目描述

蛋蛋非常热衷于挑战自我,今年暑假他准备沿川藏线骑着自行车从成都前往拉萨.

川藏线的沿途有着非常美丽的风景,但在这一路上也有着很多的艰难险阻,路况变化多端,而蛋蛋的体力十分有限,因此在每天的骑行前设定好目的地,同时合理分配好自己的体力是一件非常重要的事情.

由于蛋蛋装备了一辆非常好的自行车,因此在骑行过程中可以认为他仅在克服风阻做功(不受自行车本身摩擦力以及自行车与地面的摩擦力影响).

某一天他打算骑 段路,每一段内的路况可视为相同:对于第 段路,我们给出有关这段路况的 个参数 ,其中 表示这段路的长度, 表示这段路的风阻系数, 表示这段路上的风速( 表示在这段路上他遇到了顺风,反之则意味着他将受逆风影响).

若某一时刻在这段路上骑车速度为 ,则他受到的风阻 大小为 **(这样若在长度为 的路程内保持骑行速度$v$ 不变,则他消耗能量(做功) )**.

设蛋蛋在这天开始时的体能值是 ,请帮助他设计一种行车方案,使他在有限的体力内用最短的时间到达目的地。请告诉他最短的时间 是多少.

输入输出格式

输入格式

第一行包含一个正整数 和一个实数 ,分别表示路段的数量以及蛋蛋的体能值.

接下来$n$ 行分别描述 个路段,每行有 个实数 分别表示第 段路的长度,风阻系数以及风速.

输出格式

输出一个实数 ,表示蛋蛋到达目的地消耗的最短时间,要求至少保留到小数点后 位.

输入输出样例

输入样例#1

3 10000
10000 10 5
20000 15 8
50000 5 6

输出样例#1

12531.34496464

说明

样例说明

一种可能的方案是:蛋蛋在三段路上都采用匀速骑行的方式,其速度依次为 .

评分方法

本题没有部分分,你程序的输出只有和标准答案的差距不超过 时,才能获得该测试点的满分,否则不得分.

数据规模与约定

对于 的数据, ;

对于 的数据, ;

对于 的数据, ;

对于 的数据, ;

对于 的数据,

.

数据保证最终的答案不会超过 .

提示

必然存在一种最优的体力方案满足:蛋蛋在每段路上都采用匀速骑行的方式.

分析

给定限制:

求:

使用拉格朗日乘数法可以得到下面的式子

然后发现总耗能关于单调递减,可以二分的值,代入方程求解

关于解方程,因为关于单调递增,因此我们可以二分出这个方程的解


关于拉格朗日乘数法可以参见这篇文章

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
//**********head by yjjr**********
#define eps 1e-12
#define inf 1e9
const int maxn=5e4+6;
int n;
double e,s[maxn],k[maxn],v[maxn],x[maxn];
double calc(double ld){
	double tot=0;
	rep(i,1,n){
		double l=max(0.0,v[i]),r=inf;
		while(r-l>eps){
			double mid=(l+r)/2;
			if(2*ld*k[i]*mid*mid*(mid-v[i])>1)r=mid;
			else l=mid;
		}
		x[i]=l;
		tot+=k[i]*s[i]*(x[i]-v[i])*(x[i]-v[i]);
	}
	return tot;
}
int main()
{
	scanf("%d%lf",&n,&e);
	rep(i,1,n)scanf("%lf%lf%lf",&s[i],&k[i],&v[i]);
	double l=0,r=inf;
	while(r-l>eps){
		double mid=(l+r)/2;
		if(calc(mid)>=e)l=mid;else r=mid;
	}
	double ans=0;
	rep(i,1,n)ans+=s[i]/x[i];
	printf("%.10lf\n",ans);
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr