admin 管理员组文章数量: 887006
bzoj2876 [NOI2012]骑行川藏（拉格朗日乘数法）
题目描述
蛋蛋非常热衷于挑战自我，今年暑假他准备沿川藏线骑着自行车从成都前往拉萨。川藏线的沿途有着非常美丽的风景，但在这一路上也有着很多的艰难险阻，路况变化多端，而蛋蛋的体力十分有限，因此在每天的骑行前设定好目的地、同时合理分配好自己的体力是一件非常重要的事情。
由于蛋蛋装备了一辆非常好的自行车，因此在骑行过程中可以认为他仅在克服风阻做功（不受自行车本身摩擦力以及自行车与地面的摩擦力影响）。某一天他打算骑\(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;
}转载于:.html
本文标签： bzoj2876 NOI2012骑行川藏（拉格朗日乘数法）
版权声明：本文标题：bzoj2876 [NOI2012]骑行川藏（拉格朗日乘数法） 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732360324h1535033.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论