题目

在无穷大的水平面上有一个平面直角坐标系。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

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

1 条评论

Remmina · 2019年1月29日 9:42 下午

哦~ 哦~ 学到了

发表回复

Avatar placeholder

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