[已解决]求教一个问题的思路

Sj中国智造

请教一下这个问题的思路，只要思路就行，不用代码。

最佳答案

月排行榜 / 总排行榜

caoyueyan

2017-12-7 08:30:22

提供我的思路：士兵从分x轴移动和y轴移动两个方向移动,所以分两步
假设有n个士兵，其坐标是(x1,y1)...(xn,yn)
A.x轴移动至整齐的排列
   1求(x,0)的坐标，在x的范围内，求一个x坐标到(x1,0),(x2,0)....(xn,0)点的距离最小,x是整齐一列的中位数(奇数一个?，偶数两个?）
B.先让士兵y轴移动至y坐标相等
   1，求(0,y)的坐标,求在y范围内,求一个y坐标到这些（0，y1）,(0,y2).....(0,yn)点的距离最小


可以用中位数求解
http://blog.csdn.net/wyg1997/article/details/50969438

例题是
没排好时x坐标  1 1 2 3 3     最小是1 最大是3    1到3的中位数是2    奇数中位数在(n+1)/2点   偶数在n/2 ~ n/2+1处
排好后  0 1 2 3 4中位数是2
   
y坐标-2  2 2 3  3  中位数是2 所以 y坐标取2

所以排列好后中间那个士兵x,y坐标是(2,2)，可以推出其他士兵的坐标（0，2）（1，2）（2，2）（3，2）（4，2）
算出x轴移动了（1-0）+（1-1）+（2-2）+（3-3）+（|3-4|）=2
算出y轴移动了(|-2-2|)+(2-2)+（2-2）+（3-2）+（3-2）=6
一共移动了8

跳转到最佳答案楼层

caoyueyan

提供我的思路：士兵从分x轴移动和y轴移动两个方向移动,所以分两步
假设有n个士兵，其坐标是(x1,y1)...(xn,yn)
A.x轴移动至整齐的排列
   1求(x,0)的坐标，在x的范围内，求一个x坐标到(x1,0),(x2,0)....(xn,0)点的距离最小,x是整齐一列的中位数(奇数一个?，偶数两个?）
B.先让士兵y轴移动至y坐标相等
   1，求(0,y)的坐标,求在y范围内,求一个y坐标到这些（0，y1）,(0,y2).....(0,yn)点的距离最小


可以用中位数求解
http://blog.csdn.net/wyg1997/article/details/50969438

例题是
没排好时x坐标  1 1 2 3 3     最小是1 最大是3    1到3的中位数是2    奇数中位数在(n+1)/2点   偶数在n/2 ~ n/2+1处
排好后  0 1 2 3 4中位数是2
   
y坐标-2  2 2 3  3  中位数是2 所以 y坐标取2

所以排列好后中间那个士兵x,y坐标是(2,2)，可以推出其他士兵的坐标（0，2）（1，2）（2，2）（3，2）（4，2）
算出x轴移动了（1-0）+（1-1）+（2-2）+（3-3）+（|3-4|）=2
算出y轴移动了(|-2-2|)+(2-2)+（2-2）+（3-2）+（3-2）=6
一共移动了8

lfjking

取N 个士兵的 Y 坐标值做平均得到 排在哪行最近
取N 个士兵的 X 坐标平均值为中心将 x 坐标往中心靠拢 排成一行就行了
这样应该可以用比较少的步骤完成。
自己实现试试吧

zqianglh

1 先找到行数Y
2 用最小步去做
1） 不用动
2） 只动1步到Y的
3） 动2步到Y的
。。。。
n） 到所有人都到Y行
做个总步数求和sum(最小的先动)

Sj中国智造

lfjking 发表于 2017-12-7 10:24
取N 个士兵的 Y 坐标值做平均得到 排在哪行最近
取N 个士兵的 X 坐标平均值为中心将 x 坐标往中心靠拢 排 ...

这我试过了，有点问题，譬如5个士兵的y坐标为2，2，3，3，-3，平均值为1.4离1近，但事实上都移动到y=2时纵向移动步数最少

zqianglh

Sj中国智造 发表于 2017-12-7 13:39
这我试过了，有点问题，譬如5个士兵的y坐标为2，2，3，3，-3，平均值为1.4离1近，但事实上都移动到y=2时 ...

zqianglh

你算的是1.4到0的距离  不是到-3的
-3用0轴表示 5 5 6 6 0  就没有问题了

Sj中国智造

zqianglh 发表于 2017-12-7 16:10
你算的是1.4到0的距离  不是到-3的
-3用0轴表示 5 5 6 6 0  就没有问题了

难道不是一样吗，只不过是加了整体加了而已

zqianglh

Sj中国智造 发表于 2017-12-7 16:46
难道不是一样吗，只不过是加了整体加了而已

1.4 是算数值 不是距离值
都取正 就可用算数值表示距离值