E. Beautiful Array（题解）

原题链接：

https://codeforces.com/problemset/problem/1986/E

思路：

排序，取模， 思维

关于操作：ai=ai+k;
若要使a1+m1*k==a2+m2*k;
则当a1, a2满足a1%k==a2%k，a1,a2可以满足a1+m1*k==a2+m2*k;并在需要(|a1-a2|)/k次操作。

将a数组取模后，用vector分别储存， a1和a2相差越小， 需要的次数越小，所以用一个sort排序。

取模后相同的数的个数可以全为偶数， 也可以只有一个奇数。其他则不满足。

偶数直接处理， 奇数需要枚举要放在中间的那个数， 可以看函数mark();

代码：

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int xmmm=2e5+10;
int a[xmmm];
vector<int>s[xmmm];
int head[xmmm];
int p1[xmmm], p2[xmmm];
int s1[xmmm], s2[xmmm];
int mark(int x){
    for(int i=0;i<=head[x];i++)p1[i]=p2[i]=0;
    for(int i=0, j=1;i<head[x]-1;i+=2, j++)p1[j]=s[x][i+1]-s[x][i];
    for(int i=1, j=1;i<head[x];i+=2, j++)p2[j]=s[x][i+1]-s[x][i];
    for(int i=1;i<=head[x]/2;i++){
        s1[i]=s1[i-1]+p1[i];
        s2[i]=s2[i-1]+p2[i];
    }
    int mi=2e10;
    for(int i=0;i<head[x];i+=2){
        int ss=s1[i/2]+(s2[head[x]/2]-s2[i/2]);
        mi=min(mi, ss);
    }
    return mi;
}
void in(int t){
    for(int i=0;i<=t;i++)s[i].clear();
}
void solve(){
    int cnt=0;
    map<int, int>mp;
    int n, k;cin>>n>>k;
    for(int i=1;i<=n;i++){
        int t;cin>>t;
        if(mp[t%k]==0)mp[t%k]=++cnt;
        s[mp[t%k]].push_back(t);
    }
    int sum=0, num=0;
    for(int i=1;i<=cnt;i++){
        head[i]=s[i].size();
        if(head[i]%2)num++;
    }
    if(num>1){
        cout<<-1<<'\n';
        in(cnt);
        return ;
    }
    for(int i=1;i<=cnt;i++){
        sort(s[i].begin(), s[i].end());
        if(head[i]%2==0){
            for(int j=1;j<head[i];j+=2)sum+=(s[i][j]-s[i][j-1])/k;
        }
        else if(head[i]>1)sum+=mark(i)/k;

    }
    cout<<sum<<'\n';
    in(cnt);
}
signed main()
{
    int T;cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

总结：

sort常用
写题最大的魅力就是能不断AC和一直WA
欢迎留言！