标签：拉格朗日乘数法，二分
题目
题目描述
蛋蛋非常热衷于挑战自我,今年暑假他准备沿川藏线骑着自行车从成都前往拉萨.
川藏线的沿途有着非常美丽的风景,但在这一路上也有着很多的艰难险阻,路况变化多端,而蛋蛋的体力十分有限,因此在每天的骑行前设定好目的地,同时合理分配好自己的体力是一件非常重要的事情.
由于蛋蛋装备了一辆非常好的自行车,因此在骑行过程中可以认为他仅在克服风阻做功(不受自行车本身摩擦力以及自行车与地面的摩擦力影响).
某一天他打算骑\(n\) 段路,每一段内的路况可视为相同:对于第\(i\) 段路,我们给出有关这段路况的\(3\) 个参数\(s_i,k_i,v_i'\) ,其中\(s_i\) 表示这段路的长度,\(k_i\) 表示这段路的风阻系数,\(v_i'\) 表示这段路上的风速(\(v_i'\gt 0\) 表示在这段路上他遇到了顺风,反之则意味着他将受逆风影响).
若某一时刻在这段路上骑车速度为\(v\) ,则他受到的风阻 大小为\(F=k_i(v-v_i')^2\) **(这样若在长度为\(s\) 的路程内保持骑行速度$v$ 不变,则他消耗能量(做功)\(E=k_i(v-v_i')^2s\) )**.
设蛋蛋在这天开始时的体能值是\(E_U\) ,请帮助他设计一种行车方案,使他在有限的体力内用最短的时间到达目的地。请告诉他最短的时间\(T\) 是多少.
输入输出格式
输入格式
第一行包含一个正整数\(n\) 和一个实数\(E_U\) ,分别表示路段的数量以及蛋蛋的体能值.
接下来$n$ 行分别描述\(n\) 个路段,每行有\(3\) 个实数\(s_i,k_i,v_i'\) 分别表示第\(i\) 段路的长度,风阻系数以及风速.
输出格式
输出一个实数\(T\) ,表示蛋蛋到达目的地消耗的最短时间,要求至少保留到小数点后\(6\) 位.
输入输出样例
输入样例#1
3 10000
10000 10 5
20000 15 8
50000 5 6
输出样例#1
12531.34496464
说明
样例说明
一种可能的方案是:蛋蛋在三段路上都采用匀速骑行的方式,其速度依次为\(5.12939919,8.03515481,6.17837967\) .
评分方法
本题没有部分分,你程序的输出只有和标准答案的差距不超过\(10^{-6}\) 时,才能获得该测试点的满分,否则不得分.
数据规模与约定
对于\(10\%\) 的数据,\(n=1\) ;
对于\(40\%\) 的数据,\(n\le2\) ;
对于\(60\%\) 的数据,\(n\le100\) ;
对于\(80\%\) 的数据,\(n\le1000\) ;
对于\(100\%\) 的数据,\(n\le10^4,E_U\le10^8\)
\(s_i\in(0,10^5],k_i\in(0,15],v_i'\in(-100,100)\) .
数据保证最终的答案不会超过\(10^5\) .
提示
必然存在一种最优的体力方案满足:蛋蛋在每段路上都采用匀速骑行的方式.
分析
给定限制：
\[f(i)=\sum_{i=1}^{i<=n}s_{i}k_{i}(x_i-v_i)^2=E\]求：
\[min{\sum_{i=1}^{i<=n} \frac {s_i} {v_i}}\]使用拉格朗日乘数法可以得到下面的式子
\[{2 \lambda k_is_iv_i^2(x_i-v_i)=1}\]然后发现总耗能关于\(\lambda\)单调递减，可以二分\(\lambda\)的值，代入方程求解
关于解方程，因为\(v_i^2(x_i-v_i)\)关于\(v_i\)单调递增，因此我们可以二分出这个方程的解
关于拉格朗日乘数法可以参见这篇文章
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;
}
