求条件极值 min f(x)=∑_i s_i/x_i,g(x)=E-∑_i k_i*(x_i-v_i)²*s_i=0

构造拉格朗日函数L(x)=f(x)-λ*g(x),λ为拉格朗日乘数

则有f(x)取极值时,有L_xi(x)=0,g(x)=0

二分λ,解方程L_xi(x)=2*λ*k_i*s_i*(x_i-v_i)-s_i/x_i²=0再带入g(x)=0中去验证

整理得:2*λ*k_i*x_i²*(x_i-v_i)=1

看起来， 这个方程似乎不太好解。。。

题目中还蕴含一个条件:x_i>v_i且x_i>0，我们总不能倒着走对吧。。。

所以，这个函数在满足题意的定义域内单调，就可以二分求解了

Portal

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define eps 1e-12
#define inf 1e12
using namespace std;

const int MAXN=10005;
typedef long double db;

int n;

db x[MAXN];

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

db ans;

inline db equation(int i){
	db l=max(0.,v[i]),r=inf;
	while(r-l>eps){
		db m=(l+r)/2.;
		if(ans*2.*k[i]*(m-v[i])*m*m-1.>0)r=m;
		else l=m;
	}
	return l;
}

inline db phi(){
	db res=0;
	for(int i=1;i<=n;++i)
		res+=k[i]*s[i]*(x[i]-v[i])*(x[i]-v[i]);
	return res-E;
}

inline db calc(){
	db res=0;
	for(int i=1;i<=n;++i)
		res+=s[i]/x[i];
	return res;
}

inline void Init(){
	scanf("%d%lf",&n,&E);
	for(int i=1;i<=n;++i)
		scanf("%lf%lf%lf",s+i,k+i,v+i);
}

inline void Solve(){
	db l=0,r=inf;
	while(r-l>eps){
		ans=(l+r)/2.;
		for(int i=1;i<=n;++i)
			x[i]=equation(i);
		if(phi()>eps)l=ans;
		else r=ans;
	}
	ans=calc();
	printf("%.8f\n",(double)ans);
}

int main(){
	Init(); Solve(); return 0;
}