题目

在无穷大的水平面上有一个平面直角坐标系。N-1 条垂直于 x 轴的直线将空间分为了 N 个区域。

你被要求把 $(0,0)$处的箱子匀速推到 $(x,y)$。

箱子受水平面的摩擦力与正压力正相关，所以在每个区域的摩擦力可以表示为 $f _ i$

那么，你把箱子推到目的地做的最小功是多少呢？(不考虑改变速度时的做功)

拉格朗日乘数法

所谓拉格朗日乘数法，就是现在我有若干变量：$x _ 1,x _ 2,x _ 3,x _ 4…x _ n$，有条件 $G(x)=K$，然后要求最大/小化一个函数 $F(x)$。
这样的话，只要整出一个变量 $\lambda$，然后对于函数 $L(x)=F(x)-\lambda(G(x)-K)$，对于包括 $\lambda$在内的所有变量求偏导，当所有的偏导数都是 0 的时候，$F(x)$取到最值。

解题思路

本题中，$F(x)=sum_{i=1}^n f_i \sqrt{d_i^2+y_i^2}$，$G(x)=sum_{i=1}^n y_i=Y$，发现我们可以二分 $\lambda$，由于对每个 $y_i$求偏导的结果都要是 0。使用复合函数求导的方法，将 $L(x)$对 $x_i$求偏导的结果是 $\frac{f _ iy _ i}{\sqrt{d _ i^2+y _ i^2}}$，可以得到 $y _ i=\frac{\lambda d _ i}{\sqrt{f _ i^2-\lambda^2}}$，发现本式具有单调性，将求解出来的 $y_i$相加，看比 $Y$大还是小，就可以知道二分的这个 $\lambda$大了还是小了。
最后算一下 $F(x)$

#include<bits/stdc++.h>
using namespace std;
#define RI register int
typedef double db;
const int N=105;
const db eps=1e-7;
int n;db d[N],f[N],Y,ans;
int check(db u) {
    db y=0;
    for(RI i=1;i<=n;++i) y+=d[i]*u/sqrt(f[i]*f[i]-u*u+1e-9);
    return y>Y;
}
int main()
{
    db l,r=1e20,res=0;
    scanf("%d%lf",&n,&Y);
    for(RI i=1;i<=n;++i) scanf("%lf",&d[i]);
    for(RI i=1;i<=n;++i) scanf("%lf",&f[i]),f[i]=1/f[i],r=min(r,f[i]);
    l=-r;
    while(r-l>eps) {
        db mid=(l+r)/2.0;
        if(check(mid)) res=mid,r=mid;
        else l=mid;
    }
    for(RI i=1;i<=n;++i) ans+=d[i]*f[i]*sqrt(1+res*res/(f[i]*f[i]-res*res));
    printf("%.3lfn",ans);
    return 0;
}