题解 P2179 【[NOI2012]骑行川藏】
GKxx
2019-06-16 14:00:59
### 题意:
给出$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了...