Make Them Equal

传送门

思路很简单，但为什么总是会被细节卡 wa 啊。。。

首先很自然地把所有 \(a_i,i>1\) 都变为 \(0\) 。（注意细节优先变代价小的！！！），然后再从 \(a_1\) 分出一些给 \(a_i\) 。

（我一开始没想清楚，以为 \(a_i<\frac{sum}{n}\) 的没必要变小。但实际上只有把所有数都给 \(a_1\) 才能尽可能让 \(a_i\) 可以转化其它数到下标的倍数。很细节，但实际上更简洁也更优秀，不用分讨很多）

附上调了很多细节、冗长的代码

#include<bits/stdc++.h>
using namespace std;
int a[10005];
struct node{
	int i,j,x;
};
vector<node> ans;
node nw(int i,int j,int x){
	node ne;
	ne.i=i,ne.j=j,ne.x=x;
	return ne;
}
int main(){
	int T;cin>>T;
	while(T--){
		int n,sum=0;cin>>n;
		for(int i=1;i<=n;++i){
			cin>>a[i];sum+=a[i];
		}
		if(sum%n!=0){
			cout<<-1<<endl;
			continue;
		}
		sum/=n;
		ans.clear();
		for(int tt=1;tt<=n;++tt){
			if(a[1]>=n)break;
			int pos=2;
			for(int i=2;i<=n;++i){
				if(a[1]>=n)break;
				if(a[i]>=i){
					if(a[i]-a[i]%i>a[pos]-a[pos]%pos)pos=i;
					//a[1]+=a[i]-a[i]%i;
					//ans.push_back(nw(i,1,a[i]/i));
					//a[i]%=i;
				}
			}
			if(a[pos]>=pos){
				a[1]+=a[pos]-a[pos]%pos;
				ans.push_back(nw(pos,1,a[pos]/pos));
				a[pos]%=pos;
			}else break;
		}
	//	for(int i=1;i<=n;++i)cout<<a[i]<<" ";cout<<endl;
		for(int tt=1;tt<=n;++tt){
			for(int i=2;i<=n;++i){
				if(a[i]>0&&a[1]>=0+((i-a[i])%i+i)%i){
					if(a[i]%i!=0)ans.push_back(nw(1,i,((i-a[i])%i+i)%i));
					ans.push_back(nw(i,1,(a[i]+((i-a[i])%i+i)%i)/i));
					a[1]+=a[i]-0;
					a[i]=0;
				}
				/*if(a[i]<sum&&a[1]>=sum-a[i]){
					ans.push_back(nw(1,i,sum-a[i]));
					a[1]-=(sum-a[i]);
					a[i]=sum;
				}*/
			}
		}
		for(int tt=1;tt<=n;++tt){
			for(int i=2;i<=n;++i){
				if(a[i]>sum&&a[1]>=sum+i-a[i]){
					ans.push_back(nw(1,i,sum+i-a[i]));
					ans.push_back(nw(i,1,1));
					a[1]+=a[i]-sum;
					a[i]=sum;
				}
				if(a[i]<sum&&a[1]>=sum-a[i]){
					ans.push_back(nw(1,i,sum-a[i]));
					a[1]-=(sum-a[i]);
					a[i]=sum;
				}
			}
		}
		int pd=1;
		for(int i=1;i<=n;++i)if(a[i]!=sum)pd=0;
		if(pd==0){
			cout<<-1<<endl;
			continue;
		}
		cout<<ans.size()<<endl;
		for(int i=0;i<ans.size();++i){
			cout<<ans[i].i<<" "<<ans[i].j<<" "<<ans[i].x<<endl;
		}
	}
	return 0;
}
/*
1
22
6 12 3 14 5 4 3 15 15 8 11 6 4 18 2 6 8 24 14 2 8 32

1
5
11 19 1 1 3

3
4
2 16 4 18
6
1 2 3 4 5 6
5
11 19 1 1 3

1
10
1 1 2 3 4 4 6 5 5 9

1
10
1 2 3 2 5 4 4 7 3 9

1
46
22 2 4 11 11 1 5 1 8 6 13 2 14 12 16 16 16 18 27 19 18 12 25 21 15 18 32 38 31 16 5 42 18 37 1 10 40 36 10 28 33 29 2 28 46 13
*/