- 给定(n)对参数(s_i,k_i,v_i')，要求满足(v_ige v_i',sum_{i=1}^nk_i(v_i-v_i')^2s_ile E)，并最小化(sum_{i=1}^nfrac{s_i}{v_i})。
- (nle10^4)
拉格朗日乘数法
一个非常诡异的数学问题。
考虑我们让(v_i)取大肯定更优，因此(sum_{i=1}^nk_i(v_i-v_i')^2s_i)必然会卡到上界(E)，所以限制条件就由不等式被化为了等式。
这是一个比较经典的约束极值问题，定义：
[f(v)=sum_{i=1}^nfrac{s_i}{v_i}\
varphi(v)=sum_{i=1}^nk_i(v_i-v_i')^2s_i-E
]
现在的问题就是限制(varphi(v)=0)，求(f(v))的最小值。
把(varphi(v))乘上一个参数(lambda)与(f(v))相加得到：
[sum_{i=1}^nfrac{s_i}{v_i}+lambda(sum_{i=1}^nk_i(v_i-v_i')^2s_i-E)
]
我们对于这个式子求偏导，并要求导数全部等于(0)，得到：
[egin{cases}
forall iin[1,n],frac{s_i}{-v_i^2}+2lambda k_is_i(v_i-v_i')=0\
sum_{i=1}^nk_i(v_i-v_i')^2s_i-E=0
end{cases}
]
其中第一组式子可以约去(s_i)并改写成：
[2lambda k_i(v_i-v_i')v_i^2=1
]
二分答案
由(2lambda k_i(v_i-v_i')v_i^2=1)发现，显然(lambda)越大(v_i)越小，那么(varphi(v))也就越小。
所以说，我们可以二分(lambda)，计算出所有的(v_i)，然后把(varphi(v))与(0)比较即可。
而要求(v_i)，由于(v_ige v_i')，发现(2lambda k_i(v_i-v_i')v_i^2)是关于(v_i)递增的，因此同样可以二分答案与(1)比较。
于是这道题就做完了。
代码：(O(nlog^2V))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 10000
#define DB double
#define eps 1e-12
using namespace std;
int n;DB E,s[N+5],k[N+5],v0[N+5];
DB v[N+5];I bool Check(Con DB& x)//检验λ
{
DB l,r,mid,t=0;for(RI i=1;i<=n;t+=k[i]*(v[i]-v0[i])*(v[i]-v0[i])*s[i],++i)//t统计φ(v)
{l=max(v0[i],0.0),r=1e6;W(r-l>eps) mid=(l+r)/2,2*x*k[i]*(mid-v0[i])*mid*mid>=1?v[i]=r=mid:l=mid;}//二分v[i]
return t<=E;//比较φ(v)与0
}
int main()
{
RI i;for(scanf("%d%lf",&n,&E),i=1;i<=n;++i) scanf("%lf%lf%lf",s+i,k+i,v0+i);
DB l=0,r=1e6,mid;W(r-l>eps) Check(mid=(l+r)/2)?r=mid:l=mid;//二分λ
DB t=0;for(Check(r),i=1;i<=n;++i) t+=s[i]/v[i];return printf("%.8lf
",t),0;//计算答案
}