如果没有两个数不能相同这个限制就两个数组排序后贪心即可。现在加上这个限制，注意到每个数组中的数是两两不同的，所以每次一定能在前面或后面一个数中找一个换过来，这样每次考虑相邻三个数转移就可以了，注意特判一下边界。
1 #include<cmath> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=100005; 7 long long a[N],b[N],dp[N],n,ans; 8 inline long long diff(long long a,long long b) 9 { 10 return (a==b)?1e12:abs(a-b); 11 } 12 inline long long mini(long long a,long long b) 13 { 14 return a<b?a:b; 15 } 16 int main () 17 { 18 scanf("%lld",&n); 19 for(int i=1;i<=n;i++) 20 scanf("%lld%lld",&a[i],&b[i]); 21 sort(a+1,a+1+n),sort(b+1,b+1+n); 22 if(a[1]==b[1]&&n==1) {printf("-1"); return 0;} 23 memset(dp,0x3f,sizeof dp),dp[0]=0; 24 dp[1]=mini(dp[1],diff(a[1],b[1])); 25 dp[2]=mini(dp[2],dp[1]+diff(a[2],b[2])); 26 dp[2]=mini(dp[2],dp[0]+diff(a[1],b[2])+diff(a[2],b[1])); 27 for(int i=3;i<=n;i++) 28 { 29 dp[i]=mini(dp[i],dp[i-1]+diff(a[i],b[i])); 30 dp[i]=mini(dp[i],dp[i-2]+diff(a[i-1],b[i])+diff(a[i],b[i-1])); 31 dp[i]=mini(dp[i],dp[i-3]+diff(a[i-2],b[i])+diff(a[i-1],b[i-1])+diff(a[i],b[i-2])); 32 dp[i]=mini(dp[i],dp[i-3]+diff(a[i-2],b[i])+diff(a[i-1],b[i-2])+diff(a[i],b[i-1])); 33 dp[i]=mini(dp[i],dp[i-3]+diff(a[i-2],b[i-1])+diff(a[i-1],b[i])+diff(a[i],b[i-2])); 34 } 35 printf("%lld",dp[n]); 36 return 0; 37 }