BZOJ2876:[Noi2012]骑行川藏 拉格朗日乘数法

思路:套用拉格朗日乘数法在限制下函数最值的方法,添加未知数\(\lambda\),不过限制是什么呢?

显然能量应该满足限制.在最优意义下不难发现能量应该全部耗尽.于是需要我们最优化的函数如下:

\[min{\sum_{i=1}^{n}\frac{s_i}{v_i}+\lambda(\sum_{i=1}^{n}k_i(v_i-v_i')^2{s_i}-E)}\]

对于每个\(v_i\)求导,得到如下等式:

\[2\lambda{k_i}v_i^2(v_i-v_i')=1\]

对于\(\lambda\)求导,有:

\[\sum_{i=1}^{n}k_i(v_i-v_i')^2{s_i}=E\]

首先显然合理的\(v_i\)都应该满足\(v_i>v_i'\),我们考虑给定\(\lambda\)时,我们能够通过二分又第一种限制解出每个\(v_i\).

那么\(\lambda\)是什么?考虑第二种限制,显然左面的值是关于\(\lambda\)单调变化的,我们解出所有\(v_i\)check一下就可以通过二分解出\(\lambda\)的值了.

总之,二分套二分,时间复杂度\(O(nlog^2{n})\).

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef double f2;
 
#define N 10010
f2 s[N],k[N],_v[N];
 
f2 solve(f2 lam,int i){
    f2 L=_v[i],R=1e10,mid;
    while(R-L>1e-12){
        mid=(L+R)/2;
        if(2*lam*k[i]*mid*mid*(mid-_v[i])<1)L=mid;else R=mid;
    }return L;
}
int main(){
    int n;f2 E;scanf("%d%lf",&n,&E);
    register int i;for(i=1;i<=n;++i)scanf("%lf%lf%lf",&s[i],&k[i],&_v[i]);
     
    f2 llam=0,rlam=1e5,mid,add,tmp;
    while(rlam-llam>1e-12){
        mid=(llam+rlam)/2;
        for(add=0,i=1;i<=n;++i)tmp=solve(mid,i),add+=k[i]*s[i]*(tmp-_v[i])*(tmp-_v[i]);
        if(add>E)llam=mid;else rlam=mid;
    }
     
    f2 ans=0;for(i=1;i<=n;++i)ans+=s[i]/solve(llam,i);
     
    printf("%.10lf",ans);
     
    return 0;
}