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

题解

首先,我们可以自然的注意到,i=1将直接影响所有的数,且最终结果只会受到b[1]-a[1]的影响。

我们发现,我们始终关心的是b与a的差,因此我们其实只关心target[i]=b[i]-a[i]。
同时,我们发现整个问题中,唯一未知的是target[1]。
类似于DP。其中now[i]表示在处理到第i位时,其当前值。change[i]表示由now[i]变为target[i]所需要的操作。
于是我们可以给出下面这张表:

很自然的change[i]=target[i]-now[i]。且当我们计算出change[i]之后,我们需要据此更新$now[j \cdot i]$。而最终的结果必然是$\sum |change[i]|$。
且我们发现对于其他的i,$change[i]=x_i\cdot target[1] + y_i$。
因此我们可以根据$x_i$和$y_i$的值进行排序,使得我们可以根据target[1]的值对change[i]进行二分,使得一侧的change[i]均小于0,另一侧均大于0。

我们从i=1开始一步一步计算这个值。

当i=1时,显然一开始now[1]=0。因此change[1]=target[1]。于是我们依据change[1]更新所有的$now[j \cdot 1]$。得到下表:

当i=2时,显然change[2]=target[2]-now[2]=b[2]-a[2]-target[1]。因此此处$x_2=-1,\ y_2=b[2]-a[2]$。依次更新$now[j \cdot 2]$,得到下表:

当i=3时,change[3]=-target[1]+b[3]-a[3]。同理可得下表:

以此类推。

同时,为了使change[i]的值可以根据target[1]二分,也就是$x_i \cdot target[1] + y_i >0$。我们可以得到$target[1]>-\frac {y_i} {x_i}$,前提是$x_i>0$。
而考虑到最终影响结果的是|change[i]|,因此当$x_i<0$时,不妨取负后再加入排序。于是得到下表:

最后我们排除掉$x_i=0$的情况,对剩下的change按$\frac {y_i} {x_i}$进行排序即可。

代码

Java

Submission #135502912 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #135502722 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论