CF1416B Make Them Equal

题意：

一个数列 \(a_1 , a_2 ... a_n\) 。\((a_i \geqslant 1)\)

每次可以选一个三元组 \((x , y , z)\) 且 \(x\) 非负 ，\(a_i -= x \cdot i\) ， \(a_j += x \cdot i\) 。并且操作完之后必须保证所有 \(a_i\) 非负。

要求用不超过 \(3n\) 次操作使所有数字均分。

解法：

这题的思路比较好找，因为我们很容易发现 \(a_1\) 处最灵活，它可以随意的将任意多的 \(x\) 扔到其它堆里。所以我们用以下的操作：

1. 用 \(a_1\) 将 \(a_i\) 的数字补成 \(i\) 的倍数，然后再将 \(a_i\) 的数全部扔到 \(a_1\) 中。

2. 将 \(a_1\) 的数全部均摊到每一个 \(a_i\) 上。

这个思路非常好理解，操作数最多为 \(3(n - 1)\) 。

不过为什么能保证它每次操作完后每一项一定非负呢。

操作 2 不用解释了，均摊数值肯定不会出现负数。

而操作 1 最坏的情况就是 \(a_i\) 全部为 \(1\) ，这种情况下每次操作都会使被移动的那个结点数值为 \(0\) 。至于为什么这个情况为最坏情况就不多解释了，显然。

时间复杂度：

每组数据 \(O(n)\) ， 总复杂度 \(O(t \cdot n)\)

Code