这题用分治法怎么个解决思路?在一个划分成网络的操场上,n名士兵散乱地站在网格点上.网格点由整数坐标（x,y）表示.士兵们可以沿网格边上下左右移动一步,但在同一时刻任意网格点上只能

Question

这题用分治法怎么个解决思路?
在一个划分成网络的操场上,n名士兵散乱地站在网格点上.网格点由整数坐标（x,y）表示.士兵们可以沿网格边上下左右移动一步,但在同一时刻任意网格点上只能有一名士兵.按照军官的命令,士兵们要整齐的列成一个纵队,及排列成（x,y）,(x+1,y)…（x+n-1,y）.如何选择x和y的值才能使士兵们以最小的总移动步数排成一列.
设计一个分治算法,输出方案.
能给个代码或者伪代码就更好了,主要是思想,越快越好

Answer 1

我觉得就是二分答案.先找x,再找y.
首先这些士兵路径肯定不会交叉,交叉了肯定不是最短的.
然后,由于是网格,所以可以分离两个维度来做.
排的时候,x基本不用排,就按原来的顺序,如果有重叠的,就前后随便错开一位就行.排完之后确定一下开头,这个可以用二分答案.
排y更直接,明显的二分答案.
nlogn级别算法.