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;
}