E. Beautiful Array（cf954div3）

题意：给定一个数组，可以先对数组进行任意排序，每次操作可以选择一个ai，将它变成ai+k，

想让这个数组变成一个美丽数组（回文数组），求最少操作次数

分析：

先找出相同的数字，去掉；将取模相同的放一块，如果取模不同，无论怎么加他们都一定不会相等。放一块之后，会有两种情况，一种是偶数个，一种是奇数个。如果是偶数个，先排序，每每相邻两个可以求出最小操作次数。如果是奇数，如果只有一个数就直接放最中心，否则还要判断谁放在最中心。枚举删掉哪个数，然后前后缀和算出最小答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void sol(){
    int n,k;cin>>n>>k;
    map<int,int>mp;int t;
    for(int i=1;i<=n;i++){
        cin>>t;mp[t]++;
    }
    vector<int>a;
    for(auto&[x,y]:mp){
        if(y%2!=0){
            a.push_back(x);
        }
    }
    if(a.size()<=1){
        cout<<"0"<<endl;
        return;
    }
    map<int,vector<int>>rec;
    for(int i=0;i<a.size();i++){
        int c=a[i];
        rec[c%k].push_back(c);
    }
    ll ans=0;
    int cnt=0;
    
    for(auto& [x,cur]:rec){    
        int f=1;//0为奇数，1为偶数
        if(cur.size()%2!=0){
            cnt++;f=0;
            if(cnt>1){
            cout<<"-1"<<endl;
            return;    
            }
        }
        if(f==1){//如果是偶数
            sort(cur.begin(),cur.end());
            for(int i=1;i<cur.size();i+=2){
                ans+=(cur[i]-cur[i-1])/k;
            }
        }
        else if(cur.size()>1){//长度大于1的奇数个    
            sort(cur.begin(),cur.end());
            int m=cur.size();
            cnt++;
            vector<ll>p(m,0);
            vector<ll>s(m,0);
            p[1]=cur[1]-cur[0];
            for(int i=3;i<m;i+=2){
                p[i]=p[i-2]+cur[i]-cur[i-1];
            }
            s[m-2]=cur[m-1]-cur[m-2];
            for(int i=m-4;i>=0;i-=2){
                s[i]=s[i+2]+cur[i+1]-cur[i];
            }
            ll mi=min(p[m-2],s[1]);
            for(int i=2;i<m-2;i+=2){
                mi=min(mi,p[i-1]+s[i+1]);
            }
            ans+=mi/k;
        }
    }
    cout<<ans<<endl;
}
int main(){
    int t;cin>>t;
    while(t--)sol();
    return 0;
}