鱼C论坛

 找回密码
 立即注册
查看: 2213|回复: 8

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

[复制链接]
发表于 2017-12-7 08:30:21 | 显示全部楼层 |阅读模式
20鱼币
请教一下这个问题的思路,只要思路就行,不用代码。
最佳答案
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坐标-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
007.jpg

最佳答案

查看完整内容

提供我的思路:士兵从分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: ...
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 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坐标-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
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-12-7 10:24:48 | 显示全部楼层
取N 个士兵的 Y 坐标值做平均得到 排在哪行最近
取N 个士兵的 X 坐标平均值为中心将 x 坐标往中心靠拢 排成一行就行了
这样应该可以用比较少的步骤完成。
自己实现试试吧
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 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(最小的先动)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2017-12-7 13:39:50 From FishC Mobile | 显示全部楼层
lfjking 发表于 2017-12-7 10:24
取N 个士兵的 Y 坐标值做平均得到 排在哪行最近
取N 个士兵的 X 坐标平均值为中心将 x 坐标往中心靠拢 排 ...

这我试过了,有点问题,譬如5个士兵的y坐标为2,2,3,3,-3,平均值为1.4离1近,但事实上都移动到y=2时纵向移动步数最少
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 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时 ...


想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-12-7 16:10:30 | 显示全部楼层
本帖最后由 zqianglh 于 2017-12-7 16:12 编辑

你算的是1.4到0的距离  不是到-3的
-3用0轴表示 5 5 6 6 0  就没有问题了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2017-12-7 16:46:43 | 显示全部楼层
zqianglh 发表于 2017-12-7 16:10
你算的是1.4到0的距离  不是到-3的
-3用0轴表示 5 5 6 6 0  就没有问题了

难道不是一样吗,只不过是加了整体加了而已
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-12-7 17:18:40 | 显示全部楼层
本帖最后由 zqianglh 于 2017-12-8 11:31 编辑
Sj中国智造 发表于 2017-12-7 16:46
难道不是一样吗,只不过是加了整体加了而已


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

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 13:43

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表