题目链接：E.Two Matchings
题意
让你构造两个长为n的序列p,q，这两个序列各个位都不相同，并且满足
p
i
≠
i
且
p
p
i
=
i
{p_i≠i 且p_{p_i} =i}
pi=i且ppi=i。给你一个序列a，可以计算一个值
(
∑
i
=
1
n
a
b
s
(
a
i
−
a
p
i
)
)
/
2
{(\sum_{i=1}^{n}abs(a_i-a_{p_i}))/2}
(∑i=1nabs(ai−api))/2，找符合条件的p、q中，计算值之和最小的是多少。
题解
本题先来分析p、q序列，题目中给出
p
i
≠
i
且
p
p
i
=
i
{p_i≠i 且p_{p_i} =i}
pi=i且ppi=i，其实p,q序列相当于1，2，3…n中两两交换位置一次，由于n为偶数所以不会出现一个位置交换多次的现象。 如果要求
(
∑
i
=
1
n
a
b
s
(
a
i
−
a
p
i
)
)
/
2
{(\sum_{i=1}^{n}abs(a_i-a_{p_i}))/2}
(∑i=1nabs(ai−api))/2最小，那么我们很容易可以先确定一个序列，就是序列a排序后，每相邻两个交换即可。
那么次小值如何确定？ 如果n=4，那么次小值的序列是：4 1 3 2 如果n为6，那么次小值的序列是：6 3 2 5 4 1 一开始我在想为什么n=6时不为：3 1 4 2 6 5，最后发现这和我们第一次构造的序列：2 1 4 3 6 5最后两位相同，不合题意。
现在我们已经知道了n=4和n=6的最小值，那么我们还需要枚举n=8,10…的最小值吗。 当然不需要，
g
c
d
(
4
,
6
)
=
2
{gcd(4,6)=2}
gcd(4,6)=2，数论里由裴蜀定理得，
4
k
1
+
6
k
2
=
g
c
d
(
4
,
6
)
=
2
{4k_1+6k_2=gcd(4,6)=2}
4k1+6k2=gcd(4,6)=2是有解的，那么就代表着4的倍数和6的倍数之和一定能表示2的倍数。 言外之意知道了4和6的最小值，剩下的n(偶数)，我们可以通过递推求解。
设dp[i]：前i个数计算值之和的最小值。 初始化: dp[2]=inf dp[4]=a[4]+a[3]-a[2]-a[1] dp[6]=a[6]+a[5]-a[4]+a[3]-a[2]-a[1] 那么状态转移方程为： dp[n]=min(dp[i-4]+a[i]+a[i-1]-a[i-2]-a[i-3], dp[i-6]+a[i]+a[i-1]-a[i-2]+a[i-3]-a[i-2]-a[i-1])
代码
#include<iostream>
#include <sstream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
using namespace std
;
typedef long long ll
;
typedef long double ld
;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define lowbit(x) x&-x
const double PI
=acos(-1.0);
const double eps
=1e-6;
const ll mod
=1e9+7;
const ll inf
=1e18;
const int maxn
=2e5+10;
const int maxm
=100+10;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ll a
[maxn
];
ll dp
[maxn
];
int main()
{
int t
;
scanf("%d",&t
);
while(t
--)
{
int n
; scanf("%d",&n
);
for(int i
=1;i
<=n
;i
++) scanf("%lld",&a
[i
]);
sort(a
+1,a
+1+n
);
ll sum
=0;
for(int i
=2;i
<=n
;i
+=2) sum
+=a
[i
]-a
[i
-1];
dp
[2]=inf
;
dp
[4]=a
[4]+a
[3]-a
[2]-a
[1];
dp
[6]=a
[6]+a
[5]+a
[3]-a
[4]-a
[2]-a
[1];
for(int i
=8;i
<=n
;i
+=2)
{
dp
[i
]=min(dp
[i
-4]+(a
[i
]+a
[i
-1]-a
[i
-2]-a
[i
-3]),
(dp
[i
-6]+a
[i
]+a
[i
-1]-a
[i
-2]+a
[i
-3]-a
[i
-4]-a
[i
-5]));
}
sum
+=dp
[n
];
printf("%lld\n",sum
);
}
}
