自动搬运

查看原文

来自洛谷，原作者为

	SoyTony 不要畏惧停滞

搬运于2025-08-24 22:49:10，当前版本为作者最后更新于2023-08-24 16:13:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

考虑行 $x<y<z$，列 $l<r$，那么有三种移动方式：

• $(x,l)\to (x,r)\to (z,r)$，代价 $(r-l)a_x+(z-x)b_r$。

• $(x,l)\to (z,l)\to (z,r)$，代价 $(r-l)a_z+(z-x)b_l$。

• $(x,l)\to (y,l)\to (y,r)\to (z,r)$，代价 $(r-l)a_y+(y-x)b_l+(z-y)b_r$。

经过 $y$ 的条件时后者小于前面两个式子，移项整理得到：

$$\dfrac{a_y-a_x}{y-x}<\dfrac{b_r-b_l}{r-l}<\dfrac{a_z-a_y}{z-y} $$

因此对 $a$ 维护一下下凸壳，$b$ 同理。

现在就只考虑是向下或向右了，把前两个式子比较，有：

$$(r-l)a_x+(z-x)b_r<(r-l)a_z+(z-x)b_l\Rightarrow \dfrac{b_r-b_l}{r-l}<\dfrac{a_z-a_x}{z-x} $$

因此每次会选择沿斜率较小的方向移动，维护两个指针分别在两个凸包上移动即可。

int n,m;
int a[maxn],b[maxn];

inline bool check_slope_a(int x,int y,int z){
    ll lhs=1ll*(a[y]-a[x])*(z-y),rhs=1ll*(a[z]-a[y])*(y-x);
    return lhs>=rhs;
}
inline bool check_slope_b(int x,int y,int z){
    ll lhs=1ll*(b[y]-b[x])*(z-y),rhs=1ll*(b[z]-b[y])*(y-x);
    return lhs>=rhs;
}
inline bool check_slope_ab(int x,int y,int l,int r){
    ll lhs=1ll*(a[y]-a[x])*(r-l),rhs=1ll*(b[r]-b[l])*(y-x);
    return lhs<rhs;
}

int sta[maxn],topa;
int stb[maxn],topb;

ll ans;

int main(){
    n=read(),m=read();
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=1;i<=m;++i) b[i]=read();
    sta[++topa]=1;
    for(int i=2;i<=n;++i){
        while(topa>1&&check_slope_a(sta[topa-1],sta[topa],i)) --topa;
        sta[++topa]=i;
    }
    stb[++topb]=1;
    for(int i=2;i<=m;++i){
        while(topb>1&&check_slope_b(stb[topb-1],stb[topb],i)) --topb;
        stb[++topb]=i;
    }
    int i=1,j=1;
    while(i<topa||j<topb){
        if(i==topa){
            ans+=1ll*(stb[j+1]-stb[j])*a[sta[i]];
            ++j;
        }
        else if(j==topb){
            ans+=1ll*(sta[i+1]-sta[i])*b[stb[j]];
            ++i;
        }
        else{
            if(check_slope_ab(sta[i],sta[i+1],stb[j],stb[j+1])){
                ans+=1ll*(sta[i+1]-sta[i])*b[stb[j]];
                ++i;
            }
            else{
                ans+=1ll*(stb[j+1]-stb[j])*a[sta[i]];
                ++j;
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}