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

传送门

题意：

一个数组 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();
    }
}