Steven_MengのBlog

传送门

假设没有不允许两个相同的数配对的条件,那么直接将$AB$数组排序一遍,每一位每一位配对即可。

现在不允许两个相同的数配对,还是考虑贪心,如果出现如图的匹配情况,即$a[i]$和$b[i-alb]$匹配,其中$alb>2$。

发现这种情况肯定不是最优的,因为我们发现一定存在一个$aj$和$bk$匹配,简单的来说,就是匹配的两条直线相交,可以构造出一种更优的情况如下图。

所以我们只用考虑连续$3$个数,后面大力$dp$即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
#define MAXN 100005
#define INF 0x3f3f3f3f
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
int A[MAXN],B[MAXN],dp[MAXN];
inline int f(int a,int b){
if (a==b) return INF;
else return (a>b)?(a-b):(b-a);
}
#undef int
int main(){
#define int long long
int n=read();
for (register int i=1;i<=n;++i){
A[i]=read(),B[i]=read();
}
if (n==1&&A[1]==B[1]){
printf("-1\n");
return 0;
}
sort(A+1,A+1+n);
sort(B+1,B+1+n);
dp[0]=0;
for (register int i=1;i<=n;++i){
dp[i]=dp[i-1]+f(A[i],B[i]);
if (i>=2){
dp[i]=min(dp[i],dp[i-2]+f(A[i],B[i-1])+f(A[i-1],B[i]));
}
if (i>=3){
dp[i]=min(dp[i],dp[i-3]+f(A[i],B[i-1])+f(A[i-1],B[i-2])+f(A[i-2],B[i]));
dp[i]=min(dp[i],dp[i-3]+f(A[i-1],B[i])+f(A[i-2],B[i-1])+f(A[i],B[i-2]));
}
}
printf("%lld\n",dp[n]);
}

 评论