D. Make Them Equal(思维+构造)

https://codeforces.com/contest/1417/problem/D

---

思路：观察一下样例可以知道能构造出来的最后会变成平均值。

想着题目3*n，所以可以考虑扫三次序列。最后一次应该是把通过一个数把全部数字变成平均数。那么前两次应该是收集到一个数字上。

构造想着方便那么用i==1去构造，但是发现题目的ai只能是减，ai减到负数之类的就不好搞了。所以要尝试把后面的数都加到ai。但是直接加没法加。要使得a1加的话后面只能是减，发现后面的数要减完只能是i的倍数。所以第一次要把i=2~n全部变成i的倍数，这个理论上是可以成立的。（虽然不是很懂要怎么去证明）。第一次之后再把后面的数都放到a1去。最后由a1平均分配。

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e5+100;
typedef long long LL;
LL a[maxn];
void oper(LL i,LL j,LL x)
{
	a[i]-=i*x;
	a[j]+=i*x;
	cout<<i<<" "<<j<<" "<<x<<endl;
}
void solve()
{
	LL n;cin>>n;LL sum=0;
	for(LL i=1;i<=n;i++) cin>>a[i],sum+=a[i];
	if(sum%n) {
		cout<<"-1"<<endl;return;
	}
	cout<<3*(n-1)<<endl;
	for(LL i=2;i<=n;i++)
	{
		oper(1,i,(i-a[i]%i)%i);
		oper(i,1,a[i]/i);	
	}
	for(LL i=2;i<=n;i++)
	{
		oper(1,i,sum/n);
	}
}
int main(void)
{
  cin.tie(0);std::ios::sync_with_stdio(false);
  LL t;cin>>t;
  while(t--)
  {
  	solve();
  }
return 0;
}

 

本文地址：https://blog.csdn.net/zstuyyyyccccbbbb/article/details/108855687