题目描述

难度分:$1700$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 10^5)$、$k(1 \leq k \leq 10^9)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

你可以重排$a$。然后执行如下操作若干次：

• 选择一个下标$i$，把$a[i]$增加$k$。

输出使$a$变成回文数组的最小操作次数。如果无法做到，输出$-1$。

输入样例

11
1 1000000000
1
2 1
624323799 708290323
3 1
3 2 1
4 1
7 1 5 3
5 1
11 2 15 7 10
7 1
1 8 2 16 8 16 31
13 1
2 1 1 3 3 11 12 22 45 777 777 1500 74
10 2
1 2 1 2 1 2 1 2 1 2
11 2
1 2 1 2 1 2 1 2 1 2 1
13 3
2 3 9 14 17 10 22 20 18 30 1 4 28
5 1
2 3 5 3 5

输出样例

0
83966524
1
4
6
1
48
-1
0
14
0

算法

同余分组+前后缀分解

一个数$x$经过若干次操作后就会变为$x+t \times k$，其中$t$为非负整数。因此不管操作多少次，最终那个数对$k$取模的结果和原来的$x$对$k$取模都是一样的，所以只有模数相同的数才能在回文数组的两翼进行配对。

构建一个映射$mp$，表示“$a[i] \% k \rightarrow$ 满足这个条件的$a[i]$列表”。如果某个模数的列表长度是奇数，那这个模数的所有数字就必须在回文数组的中心，那长度为奇数的列表就不能超过$1$个，否则无解，打印$-1$。

分为以下两种情况来讨论：

1. 对于长度为偶数的列表$v$，这些数肯定是分布在回文数组的两翼，先将这些数排好序。然后相邻的两个配对，将小的数通过加$k$的方式转化为大的数，对答案的贡献为$\Sigma_{i \geq 1,i \% 2=1}\frac{v[i]-v[i-1]}{k}$。
2. 长度为奇数的列表稍微麻烦一点，需要做个前后缀分解，枚举$v[i]$作为回文数组最中心的情况。$pre[i]$表示前缀$[0,i]$中的数相邻配对的最小操作数。$suf[i]$表示后缀$[i,v.size())$中的数相邻配对的最小操作数。这两种情况都满足$i$为奇数，否则前后缀中就有奇数个元素，没办法两两配对。然后枚举$v[i]$为中心的情况：如果$i$是偶数，操作数为$pre[i-1]+suf[i+1]$；如果$i$为奇数，操作数为$pre[i-2]+suf[i+2]+\frac{v[i+1]-v[i-1]}{k}$。维护所有情况的操作数最小值，就是把中心段变为回文的最小操作数。

复杂度分析

时间复杂度

预处理出$mp$只需要遍历一遍数组$a$，时间复杂度为$O(n)$。遍历各组计算最小操作次数，其常数操作的量级也是$mp$中元素的数量，而我们仅仅是把$a$数组中的所有元素存入到了$mp$中，所以其中元素的量级为$O(n)$，计算答案的时间复杂度还是$O(n)$。

空间复杂度

在这个算法过程中，开辟的额外空间有哈希表$mp$，空间为$O(n)$。还有组大小为奇数情况下进行前后缀分解的前缀数组$pre$、后缀数组$suf$，在极端情况下，这一组就有$n$个元素，因此它们的空间消耗还是$O(n)$。整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010;
int T, n, k, a[N];

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

void solve() {
    unordered_map<int, vector<int>, custom_hash> mp;
    for(int i = 1; i <= n; i++) {
        mp[a[i] % k].push_back(a[i]);
    }
    int oddcnt = 0;
    LL ans = 0;
    for(auto&[m, v]: mp) {
        int isodd = (int)v.size()&1;
        if(isodd) {
            oddcnt++;
            if(oddcnt > 1) {
                puts("-1");
                return;
            }
        }
        sort(v.begin(), v.end());
    }
    for(auto&[m, v]: mp) {
        int sz = v.size();
        if(sz&1) {
            vector<LL> pre(sz), suf(sz);
            LL delta = 0x3f3f3f3f;
            for(int i = 1; i < sz; i += 2) {
                pre[i] = (i >= 2? pre[i - 2]: 0) + (v[i] - v[i - 1])/k;
            }
            for(int i = sz - 2; i >= 0; i -= 2) {
                suf[i] = (i + 2 < sz? suf[i + 2]: 0) + (v[i + 1] - v[i])/k;
            }
            for(int i = 0; i < sz; i++) {
                if(!(i&1)) {
                    delta = min(delta, (i > 0? pre[i - 1]: 0) + (i + 1 < sz? suf[i + 1]: 0));
                }else {
                    delta = min(delta, (i >= 2? pre[i - 2]: 0) + (i + 2 < sz? suf[i + 2]: 0) + (v[i + 1] - v[i - 1])/k);
                }
            }
            ans += delta;
        }else {
            for(int i = 1; i < sz; i += 2) {
                ans += (v[i] - v[i - 1]) / k;
            }
        }
    }
    printf("%lld\n", ans);
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &k);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        solve();
    }
    return 0;
}