首页 > 代码库 > 【bzoj2876】 Noi2012—骑行川藏

【bzoj2876】 Noi2012—骑行川藏

 http://www.lydsy.com/JudgeOnline/status.php (题目链接)

题意

  在满足约束条件$${\sum_{i=1}^ns_ik_i(v_i-v_i‘)^2=E}$$

  求$${min\sum_{i=1}^n\frac{s_i}{v_i}}$$

Solution

  像这种形式的存在一个多元函数${g(v_1,v_2,v_3,······,v_n)=E}$的约束,求解多元函数${f(v_1,v_2,v_3,······,v_n)}$的最值,我们使用拉格朗日乘子法。

  在解这道题之前,我们要知道什么是偏导数,梯度向量,等高线等等一系列的东西。当然我是不知道的,只能靠自己YY了。如果这些你都知道了,那么你应该就会知道到当${f}$取到最值时,${f}$和${g}$的等高线相切→_→,既然它们的等高线相切,那么它们的梯度向量平行${\nabla f~//~\nabla g}$。

  梯度向量的每一维就是这个函数对应那一维的偏导数$${\nabla f=(\frac{\partial f}{\partial v_1},\frac{\partial f}{\partial v_2},\frac{\partial f}{\partial v_3}······,\frac{\partial f}{\partial v_n})}$$

  因为${f}$和${g}$的梯度向量平行,我们只要知道它们在哪一个点平行,我们就解出了${v_1···v_n}$。设${\nabla f=\lambda \nabla g}$,我们可以列出${n+1}$个等式。

$${\frac{\partial f}{\partial v_1}=\lambda \frac{\partial g}{\partial v_1}}$$

$${\frac{\partial f}{\partial v_2}=\lambda \frac{\partial g}{\partial v_2}}$$

$${\frac{\partial f}{\partial v_3}=\lambda \frac{\partial g}{\partial v_3}}$$

$${······}$$

$${\frac{\partial f}{\partial v_n}=\lambda \frac{\partial g}{\partial v_n}}$$

$${g(v_1,v_2,v_3,······,v_n)=E}$$

  求出偏导数代入。

$${-\frac{s_1}{v_1^2}=2\lambda k_1s_1(v_1-v_1‘)}$$

$${-\frac{s_2}{v_2^2}=2\lambda k_2s_2(v_2-v_2‘)}$$

$${-\frac{s_3}{v_3^2}=2\lambda k_3s_3(v_3-v_3‘)}$$

$${······}$$

$${-\frac{s_n}{v_n^2}=2\lambda k_ns_n(v_n-v_n‘)}$$

$${\sum_{i=1}^nk_i(v_i-v_i‘)^2s_i=E}$$

  化简一下。

$${2\lambda k_1v_1^2(v_1-v_1‘)=-1}$$

$${2\lambda k_2v_2^2(v_2-v_2‘)=-1}$$

$${2\lambda k_3v_3^2(v_3-v_3‘)=-1}$$

$${······}$$

$${2\lambda k_nv_n^2(v_n-v_n‘)=-1}$$

$${\sum_{i=1}^nk_i(v_i-v_i‘)^2s_i=E}$$

  考虑${v_i}$的范围。如果对应的${v_i‘<0}$,吹的是逆风,那么${v_i>0}$;如果${v_i‘>0}$,吹的是顺风,那么让${v_i=v_i‘}$一定优于${v_i<v_i‘}$,于是我们得到了${v_i}$的下界。${v_i}$的上界就是把所有的能量全部用在这一段路上所能达到的最大速度(然而程序里面上界不能这样写,数据有几个点存在${s_i=0}$的情况,smg嘛→_→)。

  知道了${v_i}$的下界,那么显然${k_iv_i^2(v_i-v_i‘)>0}$,所以${\lambda<0}$。所以${v_i}$随着${\lambda}$的增大而增大,而${\sum_{i=1}^nk_i(v_i-v_i‘)^2s_i}$随着${v_i}$的增大而减小。所以我们二分${\lambda}$,进而二分求解${v_i}$,把${v_i}$代入函数${g}$,与${E}$比较比较大小来判断${\lambda}$的范围是应该往上还是往下。

细节

  公式不要写错,精度把握好。

代码

// bzoj2876#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#include<queue>#define LL long long#define inf 2147483640#define eps 1e-13#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=100010;long double s[maxn],k[maxn],v[maxn],vp[maxn],maxv[maxn],Eu;int n;long double check(long double lambda) {	long double tmp=0;	for (int i=1;i<=n;i++) {		long double l=max((long double)0.0,vp[i]),r=maxv[i];v[i]=l;		while (l<=r) {			long double mid=(l+r)/2;			if (2*lambda*mid*mid*k[i]*(mid-vp[i])>=-1) l=mid+eps,v[i]=mid;			else r=mid-eps;		}		tmp+=k[i]*(v[i]-vp[i])*(v[i]-vp[i])*s[i];	}	return tmp<=Eu;}int main() {	scanf("%d%LF",&n,&Eu);	for (int i=1;i<=n;i++) {		scanf("%Lf%Lf%Lf",&s[i],&k[i],&vp[i]);		//maxv[i]=vp[i]+sqrt(Eu/k[i]/s[i]);		maxv[i]=inf;	}	long double l=-inf,r=0,lambda;	while (l<=r) {		long double mid=(l+r)/2;		if (check(mid)) l=mid+eps,lambda=mid;		else r=mid-eps;	}	check(lambda);	long double ans=0;	for (int i=1;i<=n;i++) ans+=s[i]/v[i];	printf("%.6Lf",ans);	return 0;}

 

【bzoj2876】 Noi2012—骑行川藏