AtCoder Regular Contest 159 C

https://atcoder.jp/contests/arc159/tasks/arc159_c

题解

当最终每个数都一样时，总和一定是 $n$ 的倍数。而每次操作都是给总和加上了 $s=\dfrac{n(n+1)}{2}$。所以如果初始的总和 $sum$ 和 $sum+s$ 都不是 $n$ 的倍数那么一定无解。

否则一定有解。考虑两次操作：$(1,2,\cdots,n),(n,n-1,\cdots,1)$，所有数的相对大小没有改变。但如果交换第二次的 $n$ 和 $n-1$，就相当于是第一个数-1，第二个数+1，其它数不变。即，我们可以通过两次操作让一个数-1，同时让另一个数+1。

我们先将总和 $sum$ 调整至 $n$ 的倍数，令 $k=\dfrac{sum}{n}$。然后每次挑一个小于 $k$ 的+1，挑一个大于 $k$ 的-1，最终一定刚好全部等于 $k$。

代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int n,m,sum,a[55];
int ans[10005][55];
void modify(int x,int y)// x=x-1,y=y+1
{
    m++;
    ans[m][x]=1,ans[m][y]=2;
    int cnt=3;
    for(int i=1;i<=n;i++)
        if(i!=x&&i!=y) ans[m][i]=cnt++;
    m++;
    ans[m][x]=n-1,ans[m][y]=n;
    cnt=n-2;
    for(int i=1;i<=n;i++)
        if(i!=x&&i!=y) ans[m][i]=cnt--;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
    if(sum%n)
    {
        sum+=n*(n+1)/2;
        for(int i=1;i<=n;i++) a[i]+=i;
        m++;
        for(int i=1;i<=n;i++) ans[m][i]=i;
    }
    if(sum%n) cout<<"No"<<'\n';
    else
    {
        cout<<"Yes"<<'\n';
        int k=sum/n;
        queue<pii> q1,q2;
        for(int i=1;i<=n;i++)
        {
            if(a[i]>k) q1.push({i,a[i]-k});
            if(a[i]<k) q2.push({i,k-a[i]});
        }
        while(!q1.empty()&&!q2.empty())
        {
            if(q1.front().second==0) q1.pop();
            if(q2.front().second==0) q2.pop();
            if(q1.empty()&&q2.empty()) break;
            modify(q1.front().first,q2.front().first);
            q1.front().second--;
            q2.front().second--;
        }
        cout<<m<<'\n';
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++) cout<<ans[i][j]<<" \n"[j==n];
    }    
    return 0;
}