CF1416B Make Them Equal 题解

题意：

给出一个序列 $a$，求出一个长度不超过 $3n$ 的操作序列，使序列 $a$ 中每个元素相等。

定义一次操作为：选出 $(i,j,x)$ 三元组，满足 $i,j$ 为序列合法下标，$x$ 为 $10^9$ 以内非负整数，令 $a_i\gets a_i-x\cdot i,a_j\gets a_j+x\cdot i$。

必须保证操作过程中的任意时刻序列 $a$ 中每个元素都非负。

输出时先输出操作次数 $k$，然后输出 $k$ 行操作序列。

数据组数 $t\le10^4$，序列长度 $\sum n\le10^4$，元素大小 $1\le a_i\le10^5$。

感觉这种题目很喜欢找到一种，就像游戏机制一样的性质，使劲钻空子。

首先如果 $n \not\mid \sum a_i$ 一定无解，因为最终每个数一定会变成平均数。

注意到 $i=1$ 的自由度最高，如果所有的多余的值都放在 $i=1$ 上那么这道题就非常简单了。

考虑用以下方案移动 $i \in [2,n]$ 的 $a_i$ 的值：

用 $a_1$ 把 $a_i$ 补成 $i$ 的倍数
把 $a_i$ 移到 $a_1$ （即 $a_1 \gets a_i,~a_i \gets 0$ ）

最后，处理完所有的 $i$ 后，把 $a_1$ 均分给每个 $a_i$ 。

这个方案唯一的疑点就是第一步 $a_1$ 有没有足够的值去填补。

事实上一定是有的：显然 $a_i \ge 1$ ，因此在处理到第 $i$ 个数时 $a_1=\left(\sum_{1\le l < i}{a_l}\right) \ge i-1$ 。

这样操作数就是 $3(n-1)$ ，符合题目要求。

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int a[N];
void solve()
{
    int n, sum = 0; cin >> n;
    for(int i = 1; i <= n; i++) { cin >> a[i]; sum += a[i]; }
    if(sum % n) { cout << "-1\n"; return; }
    sum /= n; cout << 3 * (n - 1) << '\n';
    for(int i = 2; i <= n; i++)
    {
        int x = a[i] % i;
        cout << 1 << ' ' << i << ' ' << (i - x) % i << '\n';
        a[1] -= (i - x) % i; a[i] += (i - x) % i;
        cout << i << ' ' << 1 << ' ' << a[i] / i << '\n';
        a[1] += a[i]; a[i] = 0;
    }
    for(int i = 2; i <= n; i++)
    {
        cout << 1 << ' ' << i << ' ' << sum << '\n';
        a[1] -= sum; a[i] += sum;
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}