Description：

给出 $k_i,s_i,v_i$ ，并要求： $$ \sum_{i=1}^nk_i(x_i-v_i)^2s_i\leqslant E $$ 最大化： $$ f(x_1,x_2,\dots,x_n)=\sum_{i=1}^n\frac{s_i}{x_i} $$ $1\leqslant n\leqslant 10^4$

Solution：

首先那个不等号一定是要取等的，不然一定不优。

套用拉格朗日乘数法，设： $$ \varphi(x_1,x_2,\dots,x_n)=\sum_{i=1}^nk_i(x_i-v_i)^2s_i-E=0 $$ 然后设拉格朗日函数： $$ L(x_1,x_2,\dots,x_n)=f(x_1,x_2,\dots,x_n)-\lambda\varphi(x_1,x_2,\dots,x_n) $$ 分别对 $x_1,x_2,\dots,x_n,\lambda$ 在拉格朗日函数上求偏导，那么极值点就是所有的偏导数取 $0$ 的点。

对于这题： $$ L(x_1,x_2,\dots,x_n)=\sum_{i=1}^n\frac{s_i}{x_i}-\lambda\sum_{i=1}^nk_i(x_i-v_i)^2s_i $$ 对 $\lambda$ 求偏导显然就是： $$ \varphi(x_1,x_2,\dots,x_n)=\sum_{i=1}^nk_i(x_i-v_i)^2s_i-E=0 $$ 对 $x_i$ 求偏导： $$ \begin{align} L'(x_i)=(\frac{s_i}{x_i})'+(\lambda k_i(x_i-v_i)^2s_i)'&=0\\ -s_ix_i^{-2}+2\lambda k_is_i(x_i-v_i)&=0\\ 2\lambda x_i^2k_i(x_i-v_i)=1 \end{align} $$ 现在考虑怎么解这 $n+1$ 个方程，首先所有的 $x_i$ 都应大于 $v_i$ ，否则一定不优，那么 $x_i^2(x_i-v_i)$ 就是单调的，如果 $\lambda$ 确定了，我们就可以二分得到 $x_i$ ， $\lambda$ 越大， $x_i$ 越小， $\varphi$ 越小，也就是说我们可以再在外面套一个 $\lambda$ 的二分即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;double E;

#define MAXN 10010

double s[MAXN],k[MAXN],v[MAXN];

double x[MAXN];

double calc(double lambda)

{

	for(int i = 1;i <= n;++i)

	{

		double l = v[i],r = 1000000,mid;

		for(int w = 1;w <= 80;++w)

		{

			mid = (l + r) / 2;

			if(2 * lambda * mid * mid * k[i] * (mid - v[i]) > 1)r = mid;

			else l = mid;

		}

		x[i] = l;

	}

	double sum = 0;

	for(int i = 1;i <= n;++i)

	{

		sum = sum + k[i] * (x[i] - v[i]) * (x[i] - v[i]) * s[i];

	}

	return sum;

}

int main()

{

	scanf("%d%lf",&n,&E);

	for(int i = 1;i <= n;++i)

	{

		scanf("%lf%lf%lf",&s[i],&k[i],&v[i]);

	}

	double l = 0,r = 1000000,mid;

	for(int i = 1;i <= 80;++i)

	{

		mid = (l + r) / 2;

		if(calc(mid) - E < 0)r = mid;

		else l = mid;

	}

	calc(l);

	double ans = 0;

	for(int i = 1;i <= n;++i)

	{

		ans = ans + s[i] / x[i];

	}

	printf("%.10lf\n",ans);

	return 0;

}