傳送門
題意:
一個數組 a a a ,每次操作可以選擇三個數 x , y , z x,y,z x,y,z ,使得 a [ x ] − = x ∗ z a[x]-=x*z a[x]−=x∗z , a [ y ] + = x ∗ z a[y]+=x*z a[y]+=x∗z
最多做 3 n 3n 3n 次操作,問是否能将數組所有元素全部相等,輸出操作方案。
題解:
觀察發現,數組總和不變,那麼最後所有元素相等,必然這個數會是平均數,那麼判斷總和是否能除以 n n n。
考慮将所有數先都加到 a [ 1 ] a[1] a[1] 上。
1. 1. 1. 如果 a [ i ] % i = 0 a[i]\%i=0 a[i]%i=0 ,那麼 a [ i ] a[i] a[i]可以直接加到 a [ 1 ] a[1] a[1]上
2. 2. 2. 反之,設 x = i − a [ i ] % i x=i-a[i]\%i x=i−a[i]%i , 先讓 a [ 1 ] − = x a[1]-=x a[1]−=x , a [ i ] + = x a[i]+=x a[i]+=x ,那麼 a [ i ] a[i] a[i] 就能除以 i i i 。這裡有個技巧,在操作 i i i 之前 ,前面 i − 1 i-1 i−1 個數已經都加到 1 1 1 ,那麼 a [ 1 ] ≥ i − 1 a[1] \geq i-1 a[1]≥i−1 ,而 x ≤ i − 1 x \leq i-1 x≤i−1 , 是以可以保證 a [ 1 ] a[1] a[1] 不會是負數。
最後再平分到每個位置上即可。
#pragma GCC diagnostic error "-std=c++11"
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<ctime>
#define iss ios::sync_with_stdio(false)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
const int mod=1e9+7;
const int MAXN=2e5+5;
const int inf=0x3f3f3f3f;
ll a[MAXN];
struct node
{
int x, y, z;
/* data */
};
vector<node> v;
void cal(int x,int y,int z)
{
a[x] -= 1ll * x * z;
a[y] += 1ll * x * z;
v.push_back({ x, y, z });
}
int main()
{
int t;
cin >> t;
while(t--){
int n;
cin >> n;
ll sum = 0;
for (int i = 1; i <= n;i++){
cin >> a[i];
sum += a[i];
}
if(sum%n!=0){
cout << -1 << endl;
continue;
}
for (int i = 2; i <= n;i++){
if(a[i]%i==0)
cal(i, 1, a[i] / i);
else
cal(1, i, i - a[i] % i), cal(i, 1, a[i] / i);
}
for (int i = 2; i <= n;i++){
cal(1, i, sum / n);
}
cout << v.size() << endl;
for(auto i:v){
cout << i.x << " " << i.y << " " << i.z << endl;
}
v.clear();
}
}