题目描述
传送门
题目大意：你有n 个整数Ai和n 个整数Bi。你需要把它们配对，即每个Ai恰好对应一 个Bp[i]。要求所有配对的整数差的绝对值之和尽量小，但不允许两个相同的数配对
题解
这道题需要知道一个类似结论的东西：将A,B排序，每个位置与他配对的位置距离不会超过2. 具体的证明我也不会不过可以感性的理解一下。 假设没有不允许相同的数配对这个限制，那么最优的决策就是分别排序后相同位置的数配对。 现在有了限制，我们就需要交换一下配对，交换的越多和会越大，所以一定是尽可能隔着比较近的数进行交换。 如果相邻两个都与同位置的相同，那么可以使他们交换一下。 如果相邻的三个位置都相同，可以三个人换一下。最多三个一定可以存在合法的交换方案。数量再多就可以拆分。 知道了这就可以DP一下。 四种情况分类讨论一下就可以了。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 100005
#define LL long long
using namespace std;
const LL inf=
1e13;
LL f[N];
int n,a[N],b[N];
LL calc(
int x,
int y)
{
if (a[x]==b[y])
return inf;
return abs(a[x]-b[y]);
}
int main()
{
scanf(
"%d",&n);
for (
int i=
1;i<=n;i++)
scanf(
"%d%d",&a[i],&b[i]);
sort(a+
1,a+n+
1);
sort(b+
1,b+n+
1);
for (
int i=
1;i<=n;i++) f[i]=inf;
f[
0]=
0;
for (
int i=
1;i<=n;i++) {
LL t=inf;
if (i>=
1) t=min(t,f[i-
1]+calc(i,i));
if (i>=
2) t=min(t,f[i-
2]+calc(i,i-
1)+calc(i-
1,i));
if (i>=
3) t=min(t,f[i-
3]+calc(i,i-
1)+calc(i-
1,i-
2)+calc(i-
2,i)),
t=min(t,f[i-
3]+calc(i-
2,i-
1)+calc(i-
1,i)+calc(i,i-
2));
f[i]=t;
}
printf(
"%lld\n",f[n]);
}
