CF1986E Beautiful Array

传送门

Description

给定一个长度为 $n$ 的数组 ${a_i}$和正整数 $k$，数组可任意排序且不占用操作次数。一次操作可将 $a_i=a_i+k$。求最少多少次操作能将该数组变为回文数列，即保证 $a_i=a_{n - i + 1}$。

Solution

将题目转化为如何用最少次操作，得到 $\lfloor \dfrac{n}{2} \rfloor$ 对相同的元素。

将数组元素按照 \mod k 的值进行分类，使得同一类中的两个元素均可通过若干次操作后相等。

对同一类中的元素进行排序。根据一类元素数量的奇偶性分类讨论。

若一类元素有偶数个，则根据排序后的顺序，相邻元素进行若干次操作后成对相等。显然这样结果最优。

若一类元素有奇数个，定义前缀和 $suml_i$、后缀和 $sumr_i$，表示这一类的第 $i$ 元素不与其它元素匹配，$i$ 左边的元素和右边的元素完成匹配所需操作数。遍历两次即可求出前后缀和。该类元素的答案的贡献即为 $suml_i+sumr_i$ 的最小值。注意初始化时，若有这一类有 $m$ 个元素，则 $suml_0=sumr_m=0$，其余均设为极大值。

若有奇数个元素的类别超过一个，则无解，输出 -1。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef long long ll;

ll T, n, k, a[N], st[N], tot;


void WORK()
{
	ll ans = 0;
	map<ll, vector<ll> > mp;
	tot = 0;
	scanf("%lld%lld", &n, &k);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		if (mp[a[i] % k].size() == 0)
			st[++tot] = a[i] % k;
		mp[a[i] % k].push_back(a[i]);
	}
	ll cnt = 0;
	for (int i = 1; i <= tot; i++) {
		sort(mp[st[i]].begin(), mp[st[i]].end());
		if (mp[st[i]].size() % 2) {
			++cnt;
			if (mp[st[i]].size() == 1) continue;
			ll suml[N], sumr[N], sum = 1e9;
			for (int j = 0; j < mp[st[i]].size(); j++) 
				suml[j] = sumr[j] = 1e9;
			suml[0] = sumr[mp[st[i]].size() - 1] = 0;
			for (int j = 0; j < mp[st[i]].size() - 2; j += 2)
				suml[j + 2] = suml[j] + (mp[st[i]][j + 1] - mp[st[i]][j]) / k;
			for (int j = mp[st[i]].size() - 1; j > 1; j -= 2)
				sumr[j - 2] = sumr[j] + (mp[st[i]][j] - mp[st[i]][j - 1]) / k;
			for (int j = 0; j < mp[st[i]].size(); j++) {
				sum = min(sum, suml[j] + sumr[j]);
			}
			ans += sum;
		}
		else for (int j = 0; j < mp[st[i]].size(); j += 2) {
			if (j == mp[st[i]].size() - 1) ++cnt;
			ans += abs(mp[st[i]][j] - mp[st[i]][j + 1]) / k;
		}
	}
	if (cnt > 1) printf("-1\n"); 
	else printf("%lld\n", ans);
}

int main()
{
	scanf("%lld", &T);
	while (T--) WORK(); 
	return 0;
}