NOI2012骑行川藏 拉格朗日乘数法

发表于 更新于 分类于 阅读次数：

[NOI2012]骑行川藏 首先要知道偏导数，就是一个很多变量的函数求关于一个变量的导数，把其他变量看作常数。记为$\frac{\delta f}{\delta x}$ 有一个拉格朗日乘数法。给定$f(x_1,x_2,…,x_k)$，并且要求满足$g(x_1,x_2,…,x_k)=c$，求$f$的极值。 求极值的方法是这样的：我们考虑对$f$作出等高线图，并且作出$g=c$。当$g$与等高线相切时，$f$取得极值。考虑这个点两函数的梯度是成正比的，即 $$\nabla f= \lambda \nabla g$$ $$\nabla f - \lambda \nabla (g-c) = 0$$ 那么引入拉格朗日乘数$\lambda$，令$L(x_1,x_2,…,x_k,\lambda)=f(x_1,x_2,…,x_k)+\lambda (g(x_1,x_2,…,x_k)-c)$，当$L$的梯度为$0$最优，只需求出$L$的极值即可。 另一个角度：考虑对$\lambda$的偏导数，即要求$g(x_1,x_2,…,x_k)-c=0$，恰好满足了限制。 回到这个题，这个题要求$\sum_{i=1}^n s_ik_i(v_i-v’i)^2 \leq E$，求$\min \sum{i=1}^n \frac{s_i}{v_i}$ 可以发现要求最小值，$v_i$大一些是更好的，那么直接$\sum_{i=1}^n s_ik_i(v_i-v’i)^2 = E$求极值。令$f(v)=\sum{i=1}^n \frac{s_i}{v_i},g(v)=\sum_{i=1}^n s_ik_i(v_i-v’_i)^2 $，令$L(v,\lambda)=f(v)-\lambda (g(v)-E)$ 求偏导，可以得到： $$\forall i, \ \ 2\lambda k_i s_i (v_i - v’_i) - \frac{s_i}{v_i^2} = 0$$ $$\sum_{i=1}^n k_i s_i (v_i - v’_i)^2 - E = 0$$ 稍微化简可得： $$2\lambda k_i v_i^2 (v_i - v’_i) = 1$$ $$\sum_{i=1}^n k_i s_i (v_i - v’_i)^2 = E$$ 题目中的式子是有意义的，$v_i > v’_i$。考虑枚举$i$，给$v_i$钦定一个值，使得它满足第一个式子，即可求得解。不过$\lambda$也不知道，二分即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>

const int N = 1e5 + 233;
const double eps = 1e-12;

inline double pow2(double x) {
  return x * x;
}

int n; double E;
double s[N], k[N], v[N], u[N];

inline int check(double lam, double v, int i) {
  return 2 * lam * pow2(v) * k[i] * (v - u[i]) <= 1;
}

inline int check(double lam) {
  double sum = 0;
  for (int i = 1; i <= n; ++i) {
    double l = u[i] >= 0 ? u[i] : 0, r = 1e5, ans = -1;
    while (r - l > eps) {
      double mid = (l + r) / 2;
      if (check(lam, mid, i))
        ans = l = mid;
      else
        r = mid;
    }
    v[i] = ans;
    sum += k[i] * s[i] * pow2(v[i] - u[i]);
  }
  return sum <= E;
}

int main() {
  scanf("%d%lf", &n, &E);
  for (int i = 1; i <= n; ++i)
    scanf("%lf%lf%lf", s + i, k + i, u + i);
  double l = 0, r = 1e5;
  while (r - l > eps) {
    double mid = (l + r) / 2;
    if (check(mid))
      r = mid;
    else
      l = mid;
  }
  double ans = 0;
  for (int i = 1; i <= n; ++i)
    ans += s[i] / v[i];
  printf("%.10lf\n", ans);
  return 0;
}