[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也不知道,二分即可。

#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;
}

发表评论

电子邮件地址不会被公开。必填项已用 * 标注