自动搬运

查看原文

来自洛谷，原作者为

	以墨 THU大三

搬运于2025-08-24 21:45:44，当前版本为作者最后更新于2017-09-07 23:49:53，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

本题就是最小生成树模型，但只会最小生成树是不够的~~~

楼下说的其实不对，因为我就是用Kruskal算法的~

但如果你不会Kruskal也可以往下看，因为并没有涉及太多的MST知识。

推导需要一步步来哦

初始

就用最基本的最小生成树算法

把所有的区域都看成是点，每拆掉一个围栏就相当于加上一条边，这样其实就是MST了。

但是！！！不要高兴太早，关注一下本题的数量级，（1<=n,m<=25,000），然而其中的区域至少有n*m个，再加上Kruskal的排序，呵呵......

观察

注意一下，由于每一条围栏都是平行于所对应的边框的，所以，同一列的水平围栏长度相同，同一行的竖直围栏也长度相等。

这样就可以把水平围栏和竖直围栏分开算了，直接删去整行或整列。

是不是很简单？？？

但是，在删的过程中，由于到后面，并不是一整行或一整列上所有的围栏都要删去，有的删去甚至会出现环路，所以......

用x数组记录水平围栏的长度，用y数组记录竖直围栏的长度。

x1......xn+1，y1......ym+1

再用i,j两个指针记录当前扫到第几行或列。

当i,j都大于1的时候：

由于当x[i]<y[j]的时候，肯定要删第i列的水平栅栏，该列的栅栏个数为m(行数)-j(已经删了多少行)+1，对列有影响的是行（列与列不相交）

//不太理解可以自己画一个图，突然想吐槽题面的图了，居然都碎了~~~

当x[i]>y[j]的时候，肯定要删第j行的竖直栅栏，该行的栅栏个数为n(列数)-i(已经删了多少列)+1，对行有影响的是列（行与行不相交）

剩下的就看代码吧......

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=25003;
long long ans,x[N],y[N],n,m,A,B,a[N],b[N];
int i,j;
int FAST_READ()//快速读入
{
    int tot=0;char c;
    for(c=getchar();c==' '||c=='\n';c=getchar());
    while(c>='0'&&c<='9')
        tot=tot*10+c-'0',c=getchar();
    return tot;
}
int main()
{
    A=FAST_READ();B=FAST_READ();n=FAST_READ();m=FAST_READ();
    for(i=1;i<=n;i++)
        a[i]=FAST_READ();
    for(i=1;i<=m;i++)
        b[i]=FAST_READ();
    sort(a+1,a+n+1);sort(b+1,b+m+1);//注意，位置不是按升序给的
    for(i=1,x[n+1]=A-a[n];i<=n;i++)
        x[i]=a[i]-a[i-1];//记录间隔两行之间的水平围栏的长度，在0和n的位置人为加上围栏，方便计算
    for(i=1,y[m+1]=B-b[m];i<=m;i++)
        y[i]=b[i]-b[i-1];//同上
    n++;m++;
    sort(x+1,x+n+1);sort(y+1,y+m+1);//因为是最小，所以要排个序，有点贪心的感觉
    for(i=2,j=2,ans=x[1]*(m-1)+y[1]*(n-1);i<=n&&j<=m;)//i,j都为1时，预先处理
        if(x[i]<y[j])
            ans+=x[i++]*(m-j+1);
        else
            ans+=y[j++]*(n-i+1);
    printf("%lld\n",ans);
    return 0;
}