写在前面的

这个是个好东西啊，好东西啊（神志不清）。这个方法可以非常简单的求出多元函数的条件最值，而且不需要动脑子，会求导就完了。

引入

求 的最小值。其中 。

• 如果使用柯西不等式就一步。 。

• 拉格朗日乘数法的大体步骤为。

  • 令条件函数，和目标函数。
  • 分别对所有变量求出偏导。
  • 令偏导为 ，解方程。
  • 代入目标函数，得出最值。

• 但是为了讲解拉格朗日乘数法，我们令 那么定义 。那么 。现在令，所有偏导为零。可以解得方程 。最后检验得到 。

• 证明，不太会。但是可以感性理解一下，如果希望有完整证明的，可以看这个 。大概就是，在两个函数相切时。在切点处，两个函数的梯度向量是平行的，根据比例列出方程 。 。细心的朋友也行已经发现了，其实拉格朗日乘数法求出的并不是最值，而是两个函数的相切点。但是 中的函数比较平滑，直接乱搞。

  例题

  NOI2012骑行川藏

  分析

  比较模板的条件最值。我们先令出目标函数 而条件函数为 。然后就可以对这模板冲就可以了。最后列出的方程组为 。由于可以比较轻松的分析出 的单调性。所以我们考虑二分 来检验 。而 的值，通过单调性也可以二分得到。那么总复杂度为 。

  代码

  #include<bits/stdc++.h>
  using namespace std;
  #define db double
  const int N = 1e4 + 100;
  const db eps = 1e-13; 
  int n;
  db s[N],k[N],v[N],V[N],eU;
  db solve(db vi,int id,db r) {
    return (vi * vi * (vi - v[id]) * 2.0 * r * k[id]);
  }
  bool check(db m) {
    db e = 0;
    for(int i = 1;i <= n;i++) {
        db l = max(v[i],0.0),r = 1e7;
        while(l + eps <= r) {
            db mid = (l + r) / 2.0;
            if(solve(mid,i,m) <= 1.0) l = mid;
            else r = mid;
        }
        V[i] = l;
        e += k[i] * (V[i] - v[i]) * (V[i] - v[i]) * s[i];
    }
  //    printf("e: %.10f\n",e);
    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],&v[i]);
    double l = 0,r = 1e7;
    while(l + eps <= r) {
        db mid = (l + r) / 2.0;
        if(check(mid)) r = mid;
        else l = mid; 
    }
  //    printf("%.10f %.10f\n",l,r);
    db ans = 0;
    for(int i = 1;i <= n;i++) {ans += s[i] / V[i];}
    printf("%.9f\n",ans);
    return 0;
  }