Codeforces Round #754 Array Equalizer Solution (Java/C++)

Solution:

First of all, we can naturally notice that i=1 will directly affect all numbers, and the final result will only be affected by b[1]-a[1].

We found that we always care about the difference between b and a, so we actually only care about target[i]=b[i]-a[i]. At the same time, we found that in the whole problem, the only unknown is target[1].
Similar to DP. now[i] represents the current value when the processing reaches the i-th number. change[i] represents the operation required to change from now[i] to target[i].
So we can give the following table:

It is natural to change[i]=target[i]-now[i]. And when we calculated change[i], we need to update $now[j \cdot i]$ accordingly. The final result must be $\sum |change[i]|$.
And we find that for other i, $change[i]=x_i\cdot target[1] + y_i$.
Therefore, we can sort according to the value of $x_i$ and $y_i$, so that we can binary search in change[i] according to the value of target[1]. So that change[i] on one side is less than 0, and the other side is both Greater than 0.

We calculate this value step by step starting from i=1.

When i=1, obviously now[1]=0 at the beginning. Therefore change[1]=target[1]. So we update all $now[j \cdot 1]$ according to change[1]. Get the following table:

When i=2, obviously change[2]=target[2]-now[2]=b[2]-a[2]-target[1]. So here $x_2=-1,\ y_2=b[2]-a[2]$. Update $now[j \cdot 2]$ in turn, and get the following table:

When i=3, change[3]=-target[1]+b[3]-a[3]. Similarly, the following table can be obtained:

And so on.

At the same time, in order to make the value of change[i] can apply binary search according to target[1], that is, find $x_i \cdot target[1] + y_i >0$. We can get $target[1]>-\frac {y_i} {x_i}$, provided that $x_i>0$.
Considering that the final effect is |change[i]|, so when $x_i<0$, we can take the negative value before adding the sort. So get the following table:

Finally, we exclude the case of $x_i=0$ and sort the remaining change[i] by $\frac {y_i} {x_i}$.

Code:

Java

C++