D. Make Them Equal（思维)

D. Make Them Equal（思维)

思维。

思路：显然每次操作所有数之和$sum$是不变的，首先特判平均值是否存在。然后考虑将所有和先聚集到$a[1]$上，在依次分给$a[2]-a[n]$。

如果$a[i](\mathrm{m}\mathrm{o}\mathrm{d}i)=0$，显然可以将$a[i]$加到$a[1]$上，然后$a[i]=0$。

否则，就先让$a[i]$减去$i-a[i](\mathrm{m}\mathrm{o}\mathrm{d}i)$，这样就能整除。

这样的正确性：因为$a[i](\mathrm{m}\mathrm{o}\mathrm{d}i)>0$, $i-a[i](\mathrm{m}\mathrm{o}\mathrm{d}i)<i$

每轮$a[1]$都至少加$1$，所以第$i$轮$a[1]\ge i$，所以$a[1]$不会为负。

这样操作最多：$3(n-1)$次。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e4+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a,b) memset(a,b,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg register #define PII pair<int,int> #define fi first #define se second #define pb push_back #define il inline int t,n; int a[N]; vector<array<int,3> >ans; void fun(int x,int y,int z){ a[x]-=x*z,a[y]+=x*z; ans.pb({x,y,z}); } int main(){ scanf("%d",&t); while(t--){ int sum=0; scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum+=a[i]; if(sum%n) puts("-1"); else { ans.clear(); for(int i=2;i<=n;i++){ if(a[i]%i) fun(1,i,i-a[i]%i); fun(i,1,a[i]/i); } for(int i=2;i<=n;i++) fun(1,i,sum/n); printf("%d\n",ans.size()); for(auto i:ans) printf("%d %d %d\n",i[0],i[1],i[2]); } } return 0; }

---