[CF1416B] Make Them Equal

[CF1416B] Make Them Equal - 构造

Description

给出一个序列 (a)，求出一个长度不超过 (3n) 的操作序列，使序列 (a) 中每个元素相等，一次操作为：选出 ((i,j,x)) 三元组，满足 (i,j) 为序列合法下标，(x) 为 (10^9) 以内非负整数，令 (a_i:= a_i-xcdot i,a_j:=a_j+xcdot i)，须保证操作过程中的任意时刻序列每个元素都非负。

Solution

先把所有值都吞到 (a[1]) 里，然后再均分回去

均分回去只要令 ((i,j,x)) 的 (i=1, j=?, x=avg) 就可以了

吃过来时，先令 (i=1, j=id, x=(j-a[j])\%j)，再令 (i=id, j=1, x=(a[j]+(j-a[j])\%j))/j)

#include <bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
    int n;
    cin >> n;

    vector<int> a(n + 2);
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    int sum = 0;
    for (int i = 1; i <= n; i++)
        sum += a[i];
    int avg = sum / n;
    if (avg * n != sum)
    {
        cout << -1 << endl;
        return;
    }

    cout << 3 * (n - 1) << endl;
    for (int i = 2; i <= n; i++)
    {
        cout << 1 << " " << i << " " << (i - a[i] % i) % i << endl;
        cout << i << " " << 1 << " " << (a[i] + (i - a[i] % i) % i) / i << endl;
    }
    for (int i = 2; i <= n; i++)
    {
        cout << 1 << " " << i << " " << avg << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--)
        solve();
}