1 条题解
-
0
何老师 (root) LV 0 MOD @ 2022-07-12 16:51:05
对于y,相对简单,我们先将y进行排序,找到中位数设为y0,然后cnt+=|y-y0|;最后的cnt就是士兵站到同一y所需要的最少步数。
对于x,我们可以知道要使所有士兵的移动步数最小,第一个士兵应该移动进队列的第一个位置,第二个士兵应该移动进队列的第二个位置……设每个士兵的横坐标按由小到大排序后为X0,X1,X2,……所以,我们可以得出所有士兵在x方向的移动步数为|X0-x|+|X1-(x+1)|+…+|Xn-1-(x+n-1)|,将该式子变形可得|X0-x|+|(X1-1)-x|+…+|(Xn-1-(n-1))-x|,要使步数最少,则x应该为X0,X1-1,X2-2,…,Xn-1-(n-1)的中位数。将经过变化的横坐标与上述y一样的操作之后,得到的最好cnt即为最少的步数
- 1