题目

在无穷大的水平面上有一个平面直角坐标系。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;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *