CF1416B Make Them Equal(CF1416B Make Them Equal)

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\) 扔到其它堆里。所以我们用以下的操作:

  • 用 \(a_1\) 将 \(a_i\) 的数字补成 \(i\) 的倍数,然后再将 \(a_i\) 的数全部扔到 \(a_1\) 中。
  • 将 \(a_1\) 的数全部均摊到每一个 \(a_i\) 上。

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

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

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

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

时间复杂度:

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

Code

————————

CF1416B Make Them Equal

< strong > meaning of the question: < / strong >

A sequence \ (a_1, a_2… A_n \)\ ((a_i \geqslant 1)\)

One triplet \ ((x, y, z) \) can be selected at a time, and \ (x \) is non negative, \ (a_i – = x \ cdot I \), \ (a_j + = x \ cdot I \). After the operation, all \ (a_i \) must be non negative.

It is required to divide all numbers equally with no more than \ (3N \) operations.

< strong > solution: < / strong >

The idea of this question is easy to find, because it is easy to find that \ (a_1 \) is the most flexible. It can throw as many \ (x \) into other heaps at will. So we use the following operations:

  • Use \ (a_1 \) to make up the number of \ (a_i \) into the multiple of \ (I \), and then throw all the numbers of \ (a_i \) into \ (a_1 \).
  • Spread all the numbers of \ (a_1 \) equally over each \ (a_i \).

This idea is very easy to understand. The maximum number of operands is \ (3 (n – 1) \).

However, why can we ensure that each item must be non negative after each operation.

Operation 2 needs no explanation. The average value will not be negative.

The worst case of operation 1 is that all \ (a_i \) are \ (1 \). In this case, each operation will make the value of the moved node \ (0 \). As for why this is the worst case, there are few explanations, < strong > obviously < / strong >.

< strong > time complexity: < / strong >

Each group of data \ (O (n) \), total complexity \ (O (t \ cdot n) \)

Code