令 为 1 号给 2 号的金币数,负数代表反方向, 为 2 号给 3 号的金币数; 为 3 号给 4 号的金币数。
而 (m为平均数, 表示 1 号最开始的金币)
我们要求的就是
用x_i表示x_1,x_2,x_3的
ans=|x1|+|x1-G1|+|x1-G2|....
到 个点的距离和最短时,就是正解,而这个点中位数。
这里应该还有一个推导公式 : 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的中位数
就是找各点的中位数,求最短距离的题,和前几题是一样的
所以呢?
牛
共 6 条回复
这里应该还有一个推导公式 : 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的中位数
就是找各点的中位数,求最短距离的题,和前几题是一样的
所以呢?
牛