D. Make Them Equal

Codeforces Round #673 (Div. 2)

题意

根据题给的操作，让你将所有的数字都变为一样的

思路

在$3\ast n$的操作内我们去构造。

我们将所有的数先加到a[1]上，然后再去分配使每个数相等。

对于$i|a[i]$的可以直接都加到$a[1]$对于不能整除的情况可以先给$a[i]+(i-a[i]\%i)$，然后再进行操作一

算法的正确性：

https://blog.csdn.net/weixin_45750972/article/details/108916458

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; int a[maxn]; struct node{ int a,b,x; }; vector<node>ans; void f(int x,int y,int z){ a[x]-=x*z; a[y]+=x*z; ans.push_back({x,y,z}); } void solve(){ int n,sum=0;cin>>n; for(int i=1;i<=n;++i)cin>>a[i],sum+=a[i]; if(sum%n)puts("-1"); else{ ans.clear(); for(int i=2;i<=n;++i){ if(a[i]%i)f(1,i,i-a[i]%i); f(i,1,a[i]/i); } for(int i=2;i<=n;++i)f(1,i,sum/n); cout<<ans.size()<<endl; for(auto i:ans){ cout<<i.a<<" "<<i.b<<" "<<i.x<<endl; } } } signed main(){ int t;cin>>t; while(t--){ solve(); } }