# CF1416B Make Them Equal(CF1416B Make Them Equal)-其他

## CF1416B Make Them Equal(CF1416B Make Them Equal)

CF1416B Make Them Equal

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

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