题解 P2179 【[NOI2012]骑行川藏】

GKxx

2019-06-16 14:00:59

Solution

### 题意: 给出$u_1,u_2,\cdots,u_n,k_1,k_2,\cdots,k_n,s_1,s_2,\cdots,s_n$, 最小化函数$T=\sum\limits_{i=1}^n\frac{s_i}{v_i}$的值,并满足条件$\varphi=\sum\limits_{i=1}^nk_is_i(v_i-u_i)^2-E_U=0$。 原本题目描述是说$\varphi\leq0$,但一个简单的贪心思想就是能量消耗越多时间肯定越少,所以直接令$\varphi=0$即可。 ### 题解: 这是裸的条件极值,考虑拉格朗日乘数法。 首先介绍偏导数的概念:对于多元函数$y=f(x_1,x_2,\cdots,x_n)$,可以选定其中一个$x_i$视为变量,将其它的$x_j(j\neq i)$都视为常数,将$y$关于$x_i$求导,称为偏导函数,记作$\frac{\partial f}{\partial x_i}$或$f_{x_i}(x_1,x_2,\cdots,x_n)$。 拉格朗日乘数法:求函数$f(x_1,x_2,\cdots,x_n)$在满足条件$\varphi(x_1,x_2,\cdots,x_n)=0$的情况下的可能极值点,可以构造函数$L=f(x_1,x_2,\cdots,x_n)+\lambda\varphi(x_1,x_2,\cdots,x_n)$,然后联立方程组: $$\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}$$ 这里一共有$(n+1)$个方程,并且算上$\lambda$一共有$(n+1)$个未知数,可以解出若干组解,它们就是函数$f$在满足条件$\varphi=0$的情况下的所有可能极值点。 对于本题而言,设$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$关于$v_i$的偏导数为 $$ \frac{\partial L}{\partial x_i}=-\frac{s_i}{v_i^2}+2\lambda k_is_i(v_i-u_i) $$ 令上式为$0$,稍作变形得到方程 $$ 2\lambda k_i(v_i-u_i)v_i^2-1=0 $$ 注意到$v_i$必须大于等于$u_i$。因为如果$u_i\leq0$,$v_i>0>u_i$显然;而当$u_i>0$时,$v_i<u_i$意味着你在反向使劲。 并且这个方程要有解必须$\lambda>0$,因为$\lambda\leq0$时左边必然是负的。 考虑函数$g(x)=2\lambda k_i(x-u_i)x^2-1$,求导$g'(x)=6\lambda k_ix^2-4\lambda k_iu_ix$。当$\lambda>0,x\geq u_i$时$g'(x)>0$,$g(x)$单调递增。 所以对于给定的$\lambda$,我们可以二分来求解方程$g(v_i)=0$的解。 可是$\lambda$并没有给定怎么办?没有关系。从上面这个方程我们看出,$\lambda$越大,$v_i$越小,相应的$\varphi=\sum\limits_{i=1}^nk_is_i(v_i-u_i)^2-E_U$就越小。现在我们要使得$\varphi=0$,可以二分$\lambda$。 ```cpp #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$的方程可能还可以用牛顿迭代法来提高效率,可是我好像WA了...