Sj中国智造 发表于 2017-12-7 08:30:21

求教一个问题的思路

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

caoyueyan 发表于 2017-12-7 08:30:22

本帖最后由 caoyueyan 于 2017-12-8 11:39 编辑

提供我的思路：士兵从分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坐标-22 2 33中位数是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 发表于 2017-12-7 10:24:48

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

zqianglh 发表于 2017-12-7 12:50:28

本帖最后由 zqianglh 于 2017-12-7 13:02 编辑


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

Sj中国智造 发表于 2017-12-7 13:39:50

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

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

zqianglh 发表于 2017-12-7 15:55:40

本帖最后由 zqianglh 于 2017-12-7 15:58 编辑

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

zqianglh 发表于 2017-12-7 16:10:30

本帖最后由 zqianglh 于 2017-12-7 16:12 编辑

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

Sj中国智造 发表于 2017-12-7 16:46:43

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

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

zqianglh 发表于 2017-12-7 17:18:40

本帖最后由 zqianglh 于 2017-12-8 11:31 编辑

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

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

页: [1]
查看完整版本: 求教一个问题的思路