题目描述
蛋蛋非常热衷于挑战自我, 今年暑假他准备沿川藏线骑着自行车从成都前往拉萨川藏线的沿途有着非常美丽的风景, 但在这一路上也有着很多的艰难险阻, 路况变化多端, 而蛋蛋的体力十分有限, 因此在每天的骑行前设定好目的地同时合理分配好自己的体力是一件非常重要的事情
由于蛋蛋装备了一辆非常好的自行车, 因此在骑行过程中可以认为他仅在克服风阻做功 (不受自行车本身摩擦力以及自行车与地面的摩擦力影响) 某一天他打算骑 \(N\)段路, 每一段内的路况可视为相同: 对于第 \(i\)段路, 我们给出有关这段路况的 3 个参数 \(s_i ,k_i ,v_i'\) , 其中 \(s_i\) 表示这段路的长度, \(k_i\) 表示这段路的风阻系数, \(v_i'\) 表示这段路上的风速 (表示在这段路上他遇到了顺风, 反之则意味着他将受逆风影响) 若某一时刻在这段路上骑车速度为 \(v\), 则他受到的风阻大小为 \(F = k_i ( v - v_i')^2\)(这样若在长度为 \(s\)的路程内保持骑行速度 \(v\)不变, 则他消耗能量(做功)\(E = k_i ( v - vi' )^2 s\)
设蛋蛋在这天开始时的体能值是 \(Eu\) , 请帮助他设计一种行车方案, 使他在有限的体力内用最短的时间到达目的地请告诉他最短的时间 \(T\)是多少
输入输出格式
输入格式:
第一行包含一个正整数 \(N\)和一个实数 \(Eu\), 分别表示路段的数量以及蛋蛋的体能值
接下来 \(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
说明
数据规模与约定
对于 10% 的数据,\(N=1\);
对于 40% 的数据,\(N<=2\);
对于 60% 的数据,\(N<=100\);
对于 80% 的数据,\(N<=1000\);
对于所有数据,\(N \leq10000\),\(0 \leq Eu \leq 10^8,0 < s_i \leq 100000,0 < k_i \leq 1,-100 < v_i' < 100\)数据保证最终的答案不会超过 \(10^5\)
提示
必然存在一种最优的体力方案满足: 蛋蛋在每段路上都采用匀速骑行的方式
题解
先讲一讲拉格朗日乘数法:
拉格朗日乘数法是用来解决多元函数的最优值问题(最大最小)
一般形式为: 函数 \(f(x_1,x_2,x_3..x_n)\)满足限制 \(g_i(x_1,x_2,x_3...x_n)=0,(i\in 1,2,3....m)\)
解法: 定义 \(h(x_1,x_2,x_3...x_n,\lambda_1,\lambda_2,\lambda_3...\lambda_m)=f(x_1,x_2,x_3...x_n)+\Sigma_{i=1}^m\lambda_ig_i(x_1,x_2,x_3...x_n)\)
函数 \(h\)的极值就是函数 \(f\)的最优值
\(h\)极值用导数求
再回到这道题, 只需要满足一种限制:\(g(x)=\Sigma_{i=1}^n s_i\ast k_i(x_i-v_i')^2\leq Eu\), 并且, 当 \(g(x)=Eu\)时最优;
于是就有 \(g(x)\)函数:\(g(x)=\Sigma_{i=1}^n s_i\ast k_i(x_i-v_i')^2-Eu=0\)
\(f(x)\)函数为:\(f(x)=\Sigma_{i=1}^n \frac {s_i}{x_i}\),\(x_i\)为每段路的骑行速度
则 \(h(x)=\Sigma_{i=1}^n \frac{s_i}{x_i}+\lambda\ast\Sigma s_i\ast k_i(x_i-v_i')^2-Eu\)
将它求导:\(h'(x)=-\Sigma_{i=1}^n \frac{s_i}{x_i^2}+2\ast\lambda\ast\Sigma_{i=1}^n s_i\ast k_i(x_i-v_i')\)
二分求 \(h'(x)=0\)时的 \(x\)值
二分时每一个 \(x_i\)也是二分求
- #include<iostream>
- #include<cstdio>
- #include<cmath>
- #include<algorithm>
- #include<string>
- #include<cstring>
- #include<queue>
- #include<stack>
- #include<set>
- #include<bitset>
- #include<vector>
- #include<cstdlib>
- #define QAQ int
- #define TAT long long
- #define OwO bool
- #define ORZ double
- #define F(i,j,n) for(QAQ i=j;i<=n;++i)
- #define E(i,j,n) for(QAQ i=j;i>=n;--i)
- #define MES(i,j) memset(i,j,sizeof(i))
- #define MEC(i,j) memcpy(i,j,sizeof(j))
- using namespace std;
- const QAQ N=10005;
- QAQ n;
- ORZ m;
- struct data{
- ORZ s,k,v;
- }a[N];
- ORZ l,r,ans,v[N];
- OwO pd(ORZ lmd){
- F(i,1,n){
- ORZ l=a[i].v,r=1000000,ans=0;
- F(j,1,100){
- ORZ mid=(l+r)/2.0;
- if(2*lmd*a[i].k*mid*mid*(mid-a[i].v)<=1.0) l=mid,ans=mid;
- else r=mid;
- }
- v[i]=ans;
- }
- ORZ ans=0;
- F(i,1,n) ans+=a[i].k*(v[i]-a[i].v)*(v[i]-a[i].v)*a[i].s;
- return ans>=m;
- }
- QAQ main(){
- scanf("%d%lf",&n,&m);
- F(i,1,n) scanf("%lf%lf%lf",&a[i].s,&a[i].k,&a[i].v);
- l=0;r=10000000;
- F(i,1,100){
- ORZ mid=(l+r)/2.0;
- if(pd(mid)) l=mid;
- else r=mid;
- }
- F(i,1,n) ans+=a[i].s/v[i];
- printf("%.6lf\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2504944.html