http://www.lydsy.com/JudgeOnline/problem.php?id=2876 (题目链接)
在满足约束条件$${\sum_{i=1}^ns_ik_i(v_i-v_i')^2=E}$$
求$${min\sum_{i=1}^n\frac{s_i}{v_i}}$$
像这种形式的存在一个多元函数${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}$的范围是应该往上还是往下。
公式不要写错，精度把握好。
转载于:https://www.cnblogs.com/MashiroSky/p/6368825.html
