[NOI]骑行川藏 题解

传送门

题意：

给出 u 1 , u 2 , ⋯   , u n , k 1 , k 2 , ⋯   , k n , s 1 , s 2 , ⋯   , s n u_1,u_2,\cdots,u_n,k_1,k_2,\cdots,k_n,s_1,s_2,\cdots,s_n u1​,u2​,⋯,un​,k1​,k2​,⋯,kn​,s1​,s2​,⋯,sn​，

最小化函数 T = ∑ i = 1 n s i v i T=\sum\limits_{i=1}^n\frac{s_i}{v_i} T=i=1∑n​vi​si​​的值，并满足条件 φ = ∑ i = 1 n k i s i ( v i − u i ) 2 − E U = 0 \varphi=\sum\limits_{i=1}^nk_is_i(v_i-u_i)^2-E_U=0 φ=i=1∑n​ki​si​(vi​−ui​)2−EU​=0。

原本题目描述是说 φ ≤ 0 \varphi\leq0 φ≤0，但一个简单的贪心思想就是能量消耗越多时间肯定越少，所以直接令 φ = 0 \varphi=0 φ=0即可。

题解：

这是裸的条件极值，考虑拉格朗日乘数法。

首先介绍偏导数的概念：对于多元函数 y = f ( x 1 , x 2 , ⋯   , x n ) y=f(x_1,x_2,\cdots,x_n) y=f(x1​,x2​,⋯,xn​)，可以选定其中一个 x i x_i xi​视为变量，将其它的 x j ( j ≠ i ) x_j(j\neq i) xj​(j̸​=i)都视为常数，将 y y y关于 x i x_i xi​求导，称为偏导函数，记作 ∂ f ∂ x i \frac{\partial f}{\partial x_i} ∂xi​∂f​或 f x i ( x 1 , x 2 , ⋯   , x n ) f_{x_i}(x_1,x_2,\cdots,x_n) fxi​​(x1​,x2​,⋯,xn​)。

拉格朗日乘数法：求函数 f ( x 1 , x 2 , ⋯   , x n ) f(x_1,x_2,\cdots,x_n) f(x1​,x2​,⋯,xn​)在满足条件 φ ( x 1 , x 2 , ⋯   , x n ) = 0 \varphi(x_1,x_2,\cdots,x_n)=0 φ(x1​,x2​,⋯,xn​)=0的情况下的可能极值点，可以构造函数 L = f ( x 1 , x 2 , ⋯   , x n ) + λ φ ( x 1 , x 2 , ⋯   , x n ) L=f(x_1,x_2,\cdots,x_n)+\lambda\varphi(x_1,x_2,\cdots,x_n) L=f(x1​,x2​,⋯,xn​)+λφ(x1​,x2​,⋯,xn​)，然后联立方程组：

{ ∂ L ∂ x 1 = 0 ∂ L ∂ x 2 = 0 ⋯ ∂ L ∂ x n = 0 φ ( x 1 , x 2 , ⋯   , x n ) = 0 \begin{cases} \frac{\partial L}{\partial x_1}=0\\ \frac{\partial L}{\partial x_2}=0\\ \cdots\\ \frac{\partial L}{\partial x_n}=0\\ \varphi(x_1,x_2,\cdots,x_n)=0 \end{cases} ⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​∂x1​∂L​=0∂x2​∂L​=0⋯∂xn​∂L​=0φ(x1​,x2​,⋯,xn​)=0​

这里一共有 ( n + 1 ) (n+1) (n+1)个方程，并且算上 λ \lambda λ一共有 ( n + 1 ) (n+1) (n+1)个未知数，可以解出若干组解，它们就是函数 f f f在满足条件 φ = 0 \varphi=0 φ=0的情况下的所有可能极值点。

对于本题而言，设 L = T + λ φ = ∑ i = 1 n s i v i + λ ( ∑ i = 1 n k i s i ( v i − u i ) 2 − E U ) L=T+\lambda\varphi=\sum\limits_{i=1}^n\frac{s_i}{v_i}+\lambda\left(\sum\limits_{i=1}^nk_is_i(v_i-u_i)^2-E_U\right) L=T+λφ=i=1∑n​vi​si​​+λ(i=1∑n​ki​si​(vi​−ui​)2−EU​)

那么 L L L关于 v i v_i vi​的偏导数为

∂ L ∂ x i = − s i v i 2 + 2 λ k i s i ( v i − u i ) \frac{\partial L}{\partial x_i}=-\frac{s_i}{v_i^2}+2\lambda k_is_i(v_i-u_i) ∂xi​∂L​=−vi2​si​​+2λki​si​(vi​−ui​)

令上式为 0 0 0，稍作变形得到方程

2 λ k i ( v i − u i ) v i 2 − 1 = 0 2\lambda k_i(v_i-u_i)v_i^2-1=0 2λki​(vi​−ui​)vi2​−1=0

注意到 v i v_i vi​必须大于等于 u i u_i ui​。因为如果 u i ≤ 0 u_i\leq0 ui​≤0， v i &gt; 0 &gt; u i v_i&gt;0&gt;u_i vi​>0>ui​显然；而当 u i &gt; 0 u_i&gt;0 ui​>0时， v i &lt; u i v_i&lt;u_i vi​<ui​意味着你在反向使劲。

并且这个方程要有解必须 λ &gt; 0 \lambda&gt;0 λ>0，因为 λ ≤ 0 \lambda\leq0 λ≤0时左边必然是负的。

考虑函数 g ( x ) = 2 λ k i ( x − u i ) x 2 − 1 g(x)=2\lambda k_i(x-u_i)x^2-1 g(x)=2λki​(x−ui​)x2−1，求导 g ′ ( x ) = 6 λ k i x 2 − 4 λ k i u i x g&#x27;(x)=6\lambda k_ix^2-4\lambda k_iu_ix g′(x)=6λki​x2−4λki​ui​x。当 λ &gt; 0 , x ≥ u i \lambda&gt;0,x\geq u_i λ>0,x≥ui​时 g ′ ( x ) &gt; 0 g&#x27;(x)&gt;0 g′(x)>0， g ( x ) g(x) g(x)单调递增。

所以对于给定的 λ \lambda λ，我们可以二分来求解方程 g ( v i ) = 0 g(v_i)=0 g(vi​)=0的解。

可是 λ \lambda λ并没有给定怎么办？没有关系。从上面这个方程我们看出， λ \lambda λ越大， v i v_i vi​越小，相应的 φ = ∑ i = 1 n k i s i ( v i − u i ) 2 − E U \varphi=\sum\limits_{i=1}^nk_is_i(v_i-u_i)^2-E_U φ=i=1∑n​ki​si​(vi​−ui​)2−EU​就越小。现在我们要使得 φ = 0 \varphi=0 φ=0，可以二分 λ \lambda λ。

#include <cstdio>#include <climits>#include <cmath>#include <algorithm>const int maxn = 1e4 + 7;const double eps = 1e-12, inf = 1e5;int n;double eu, s[maxn], k[maxn], u[maxn], v[maxn];inline bool check(double lambda) {double e = 0;for (int i = 1; i <= n; ++i) {double left = std::max(u[i], 0.0), right = inf;while (right - left >= eps) {double mid = (left + right) / 2.0;if (2 * lambda * k[i] * (mid - u[i]) * mid * mid >= 1)right = mid;else left = mid;}v[i] = left;e += k[i] * s[i] * (v[i] - u[i]) * (v[i] - u[i]);}return e >= eu;}int main() {scanf("%d%lf", &n, &eu);for (int i = 1; i <= n; ++i) scanf("%lf%lf%lf", s + i, k + i, u + i);double left = 0, right = inf;while (right - left >= eps) {double mid = (left + right) / 2.0;if (check(mid)) left = mid;else right = mid;}double t = 0;for (int i = 1; i <= n; ++i) t += s[i] / v[i];printf("%.8lf\n", t);return 0;}

求解那个偏导数 = 0 =0 =0的方程可能还可以用牛顿迭代法来提高效率，可是我好像WA了…

如果觉得《[NOI]骑行川藏 题解》对你有帮助，请点赞、收藏，并留下你的观点哦！