题解

root 站长 2019-04-10 11:46:44 2020-06-21 16:06:43 16

为 1 号给 2 号的金币数,负数代表反方向, 为 2 号给 3 号的金币数; 为 3 号给 4 号的金币数。


(m为平均数, 表示 1 号最开始的金币)

我们要求的就是

用x_i表示x_1,x_2,x_3的

ans=|x1|+|x1-G1|+|x1-G2|....

个点的距离和最短时,就是正解,而这个点中位数。

共 6 条回复

zyl

这里应该还有一个推导公式 : a1-x1+xn=m a2-x2+x1=m .. 可得x2=x1+a2-m x3=x2+a3-m=x1+(a2-m+a3-m) 设di=ai-m; 则 xi=x1+(di+d(i-1)+....d2) 设 sum[i] 表示di 的前缀和; 则 xi=x1+sum[i]-d1; 设 sum[i]-d1=ti; 要求的就是 |x1| +|x1+t2|+|x1+t3|+.....|x1+tn|; 就是求x1点到前缀和这些点的最短距离,那就是前缀和sum的中位数

18618326610
18618326610
Yang_

就是找各点的中位数,求最短距离的题,和前几题是一样的

Xionghaoyu straight a student

所以呢?

ybt