自动搬运

查看原文

来自洛谷，原作者为

	浅色调 **

搬运于2025-08-24 21:38:27，当前版本为作者最后更新于2018-06-01 18:56:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Solution：

这个贪心神了。。。～

我们首先考虑没有限制条件，即不需要满足配对时$a_i\neq b_i$这个条件，那么很容易想到贪心的思路，直接对$a,b$从小到大排一遍序，然后累加同项之差相减的绝对值即可。

但是现在有了限制，各种方法骚，没有刚过，感觉完全不可做。

后面仔细看题，发现一个超级重要的条件，保证$a$中数各不相同，$b$中数各不相同。

那么就好搞了，我们先对$a,b$各自从小到大排一遍序，然后进行以下操作：

首先考虑输出$-1$的情况：很显然只有当序列长度为$1$且$a_1=b_1$时无解，因为当$n\geq 2$时，由于数各不相同，那么同一个数$a,b$中顶多各自出现一次，我们就可以用后面的数和前面的数配对（显然一定不会相等）。

其次，当有解时，我们贪心的想到，因为每个数顶多在$a,b$中各出现一次，所以当某次$a_i=b_i$时，则$a_i\neq b_{i-1}$且$a_i\neq b_{i+1}$（$b_i$同理），于是我们可以让其和$a_{i-1},b_{i-1}$或者$a_{i+1},b_{i+1}$搭配，或者三个互相搭配，在中间取最小值就好了。（即使这三对数，每对相同，但由于$a,b$中数各自不同，那么这三对数一定可以搭配出两两不同的情况）

那么由于前两次需要判断边界，且$i+1$可能越界。于是将过程改为$a_i,a_{i-1},a_{i-2}$三个比较取最小值（都一样的）。

排序后，求解的整个过程是线性的，于是用$DP$的思想来转移实现。

定义状态$f[i]$表示前$i$个配对能得到的最小值，因为每次转移是三个比较，则初值$f[1]=|a_1-b_1|$，$f[2]=min(f[1]+|a2-b2|,|a1-b2|+|a2-b1|)$（注意当配对的两个数相等时，将其算出的值赋为$inf$）。

那么不难得出状态转移方程：

$f[i]=f[i-1]+|a_i-b_i|$（直接配对$a_i$和$b_i$）

$f[i]=min(f[i],f[i-2]+|a_i-b_{i-1}|+|a_{i-1}-b_i|)$（$i$和$i-1$配对）

$f[i]=min(f[i],f[i-3]+|a_i-b_{i-2}|+|a_{i-1}-b_{i-1}|+|a_{i-2}-b_i|)$（三个配对时，让$i$和$i-2$配对）

$f[i]=min(f[i],f[i-3]+|a_i-b_{i-2}|+|a_{i-1}-b_i|+|a_{i+1}-b_{i-1}|)$（三个配对时，$a,b$两两匹配的一种情况）

$f[i]=min(f[i],f[i-3]+|a_i-b_{i-1}|+|a_{i-1}-b_{i-2}|+|a_{i+1}-b_i|)$（三个配对时，$a,b$两两匹配的另一种情况）

最后目标状态$f[n]$就是答案。

$\quad\;\;$欢迎来踩博客：five20（蒟蒻写题解不易，转载请注明出处，万分感谢！）

代码：

#include<bits/stdc++.h>
#define il inline
#define ll long long
#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define Min(a,b) ((a)>(b)?(b):(a))
#define la(a,b) ((a!=b)?((a-b)>0?(a-b):(b-a)):233333333)
using namespace std;
const int N=100005;
ll n,f[N],a[N],b[N];

il int gi(){
    int a=0;char x=getchar();bool f=0;
    while((x<'0'||x>'9')&&x!='-')x=getchar();
    if(x=='-')x=getchar(),f=1;
    while(x>='0'&&x<='9')a=(a<<3)+(a<<1)+x-48,x=getchar();
    return f?-a:a;
}

int main(){
    n=gi();
    For(i,1,n) a[i]=gi(),b[i]=gi();
    sort(a+1,a+n+1);sort(b+1,b+n+1);
    if(a[1]==b[1]&&n==1){cout<<-1;return 0;}
    f[1]=la(a[1],b[1]);
    f[2]=Min(f[1]+la(a[2],b[2]),la(a[1],b[2])+la(a[2],b[1]));
    For(i,3,n){
        f[i]=f[i-1]+la(a[i],b[i]);
        f[i]=Min(f[i],f[i-2]+la(a[i],b[i-1])+la(a[i-1],b[i]));
        f[i]=Min(f[i],f[i-3]+la(a[i],b[i-2])+la(a[i-2],b[i])+la(a[i-1],b[i-1]));
        f[i]=Min(f[i],f[i-3]+la(a[i],b[i-1])+la(a[i-1],b[i-2])+la(a[i-2],b[i]));
        f[i]=Min(f[i],f[i-3]+la(a[i],b[i-2])+la(a[i-1],b[i])+la(a[i-2],b[i-1]));
    }
    cout<<f[n];
    return 0;
}