传送门
Description
给定一个长度为 n 的数组 ai和正整数 k，数组可任意排序且不占用操作次数。一次操作可将 ai=ai+k。求最少多少次操作能将该数组变为回文数列，即保证 ai=an−i+1。
Solution
将题目转化为如何用最少次操作，得到 ⌊2n⌋ 对相同的元素。
将数组元素按照 modk 的值进行分类，使得同一类中的两个元素均可通过若干次操作后相等。
对同一类中的元素进行排序。根据一类元素数量的奇偶性分类讨论。
若一类元素有偶数个，则根据排序后的顺序，相邻元素进行若干次操作后成对相等。显然这样结果最优。
若一类元素有奇数个，定义前缀和 sumli、后缀和 sumri，表示这一类的第 i 元素不与其它元素匹配，i 左边的元素和右边的元素完成匹配所需操作数。遍历两次即可求出前后缀和。该类元素的答案的贡献即为 sumli+sumri 的最小值。注意初始化时，若有这一类有 m 个元素，则 suml0=sumrm=0，其余均设为极大值。
若有奇数个元素的类别超过一个，则无解，输出 -1。
Code
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
50
51
52
53
54
| #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;
}
|