题意:给定一个数组,可以先对数组进行任意排序,每次操作可以选择一个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;
}