题意

给出\(s_i, k_i, v_i', E\)，满足\(\sum_{i=1}^{n} k_i s_i ( v_i - v_i' )^2 \le E, v_i > v_i'\)，最小化$ \sum_{i=1}^{n} \frac{s_i}{v_i} $

分析

首先是贪心，很显然小于等于号要取等号，即问题转化为，满足\(g(V) = \sum_{i=1}^{n} k_i s_i ( v_i - v_i' )^2 = E\)，最小化$ f(V) = \sum_{i=1}^{n} \frac{s_i}{v_i}$。于是拉格朗日乘数大法好。

题解

拉格朗日乘数：

满足\(g(X) = c\)，最大（小）化\(f(X)\)，其中\(X\)是向量。

大概就是令\(F(X, \lambda) = f(X) + \lambda (g(X) - c)\)，得到\(|X|+1\)个偏导为0的方程，答案就是所有解的其中一个。

对于本题:

对

$$ \begin{align} F(V, \lambda) & = f(V) + \lambda (g(V) - E) \\ & = \sum_{i=1}^{n} \left( \frac{s_i}{v_i} + \lambda k_i s_i ( v_i - v_i' )^2 \right) - \lambda E \\ & = \sum_{i=1}^{n} \left( \frac{s_i}{v_i} + \lambda k_i s_i v_i^2 + \lambda k_i s_i {v'}_i^2 - 2\lambda k_i s_i v'_i v_i \right) - \lambda E \\ \end{align} $$

解出偏导方程，得到:

$$ 2 \lambda k_i v_i^2 (v_i - v'_i) - 1 = 0 $$

由于\(v_i > v_i'\)，所以对于答案的解来说，\(\lambda>0\)。而且还可以发现\(v_i\)关于\(\lambda\)单调，然后得到\((v_i - v ' _ i)\)关于\(\lambda\)单调。所以\(g(V)\)关于\(\lambda\)单调，于是我们可以二分一下\(\lambda\)。得到了\(\lambda\)，求\(v_i\)也可以二分，或者牛顿迭代。

反思

1、数学太弱。

#include 
    
     using namespace std;typedef double lf;const lf oo=1e9, eps=1e-12;const int N=10005;lf s[N], k[N], vv[N], v[N];int n;inline lf sqr(lf a) {    return a*a;}lf got(lf lambda) {    lf e=0;    for(int i=1; i<=n; ++i) {        lf l=0, r=oo, go=1/(lambda*k[i]*2);        while(r-l>=eps) {            lf mid=(l+r)/2;            if(sqr(mid)*(mid-vv[i])<=go) {                l=mid;            }            else {                r=mid;            }        }        v[i]=(l+r)/2;        e+=k[i]*s[i]*sqr(v[i]-vv[i]);    }    return e;}int main() {    lf E, l=0, r=oo;    scanf("%d%lf", &n, &E);    for(int i=1; i<=n; ++i) {        scanf("%lf%lf%lf", &s[i], &k[i], &vv[i]);    }    while(r-l>=eps) {        lf mid=(l+r)/2;        if(got(mid)<=E) {            r=mid;        }        else {            l=mid;        }    }    got((l+r)/2);    lf ans=0;    for(int i=1; i<=n; ++i) {        ans+=s[i]/v[i];    }    printf("%.9f\n", ans);    return 0;}