CF1416B Make Them Equal 题解

解题思路

观察可以发现，每次操作后序列元素之和不变，那么我们可以将每一次操作看作是 \(a_i\) 向 \(a_j\) 移动了 \(i\times x\)。由此可得，若序列和 \(sum\bmod n\not=0\)，那么一定无解，否则一定存在一个合法的操作方案。

因为每次移动时移动的数应为 \(i\) 的倍数，所以 \(a_1\) 可以向任意元素移动任意大小不超过 \(a_1\) 的数，那么我们考虑先将所有数全部移动到 \(a_1\)，再由 \(a_1\) 平分给 \(a_2,\dots,a_n\)。但是这种情况先可能存在一个 \(a_j\) 使得 \(a_j\) 不能整除 \(j\)，那么我们需要使用 \(a_1\) 先将 \(a_j\) 补为 \(j\) 的倍数然后再全部移向 \(a_1\)。

AC 代码

#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>
#include<set>
#define N 100005

int n,a[N],sum,mint[N];
struct ANS{
    int i,j,x;
};

struct Point{
    int cos;
    int val;
    int pos;
};
struct cmp{
    inline bool operator ()(
        const Point A,
        const Point B
    ) const {
        if(A.cos!=B.cos)
            return A.cos<B.cos;
        return A.val>B.val;
    }
};
inline void work(){
    scanf("%d",&n);sum=0;
    std::vector<ANS> ans;
    for(register int i=1;i<=n;++i)
        scanf("%d",&a[i]),sum+=a[i];
    if(sum%n!=0){puts("-1");return;}

    int Average=sum/n;
    
    for(register int i=2;i<=n;++i){
        int res=i-(a[i]%i);if(a[i]%i){
            ans.push_back({1,i,res});
            a[1]-=res,a[i]+=res;
        }ans.push_back({i,1,a[i]/i});
    }

    for(register int i=2;i<=n;++i)
        ans.push_back({1,i,Average});

    printf("%d\n",ans.size());
    for(auto now:ans){
        printf("%d ",now.i);
        printf("%d ",now.j);
        printf("%d\n",now.x);
    }
}
signed main(){
    int T;scanf("%d",&T);
    while(T--) work();
}