题目描述
传送门
题目大意：你有n 个整数Ai和n 个整数Bi。你需要把它们配对，即每个Ai恰好对应一 个Bp[i]。要求所有配对的整数差的绝对值之和尽量小，但不允许两个相同的数配 对。
题解
这题并没有想出来。。。 首先排序，一个结论是一个数配对的数与其距离不会超过2，也就是最多一个3的置换 这个证明的话，直观的理解是如果没有冲突的，直接对应位置配对就好了，然后有冲突的话应该尽量减少置换的大小，所以3以上的都是不被允许的 不过证明的话，可以发现大小为4的置换是可以直接证明的，而4以上的置换我不会怎么一一证明或者推出一般性。。 有了这个结论之后f(i)表示前i对配对的最优值，直接dp就行了
代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define N 100005
int n,a[N],b[N];
long long inf,f[N];
int Abs(
int x){
return (x>
0)?x:-x;}
long long calc(
int x,
int y)
{
if (x==y)
return inf;
return (
long long)Abs(x-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);
memset(f,
127,
sizeof(f));inf=f[
0];f[
0]=
0;
for (
int i=
1;i<=n;++i)
{
long long x,y,z;
if (f[i-
1]!=inf)
{
x=calc(a[i],b[i]);
if (x!=inf) f[i]=min(f[i],f[i-
1]+x);
}
if (i>=
2)
{
x=calc(a[i],b[i-
1]),y=calc(a[i-
1],b[i]);
if (x!=inf&&y!=inf) f[i]=min(f[i],f[i-
2]+x+y);
}
if (i>=
3)
{
x=calc(a[i-
2],b[i]),y=calc(a[i-
1],b[i-
1]),z=calc(a[i],b[i-
2]);
if (x!=inf&&y!=inf&&z!=inf) f[i]=min(f[i],f[i-
3]+x+y+z);
x=calc(a[i-
2],b[i-
1]),y=calc(a[i-
1],b[i]),z=calc(a[i],b[i-
2]);
if (x!=inf&&y!=inf&&z!=inf) f[i]=min(f[i],f[i-
3]+x+y+z);
x=calc(a[i-
2],b[i]),y=calc(a[i-
1],b[i-
2]),z=calc(a[i],b[i-
1]);
if (x!=inf&&y!=inf&&z!=inf) f[i]=min(f[i],f[i-
3]+x+y+z);
}
}
printf(
"%lld\n",f[n]);
}
