【西南科技大学】算法报告4
需积分: 0 34 浏览量
2022-11-16
14:31:19
上传
评论 1
收藏 149KB DOCX 举报
2021-2022-1 学期《算法设计与分析》实验报告
1 / 5
Soldiers 研究报告
学号：___________ 姓名：__________
一、目的：
在一个划分成网格的操场上，n 个士兵散乱地站在网格点上。网格点由整数
坐标(x,y)表示。士兵们可以沿网格边上、下、左、右移动一步，但在同一时刻任
一网格点上只能有一名士兵。按照军官的命令，士兵们要整齐地列成一个水平队
列，即排列成(x,y),(x+1,y),…,(x+n-1,y)。如何选择 x 和 y 的值才能使士兵们以最少
的总移动步数排成一列。计算使所有士兵排成一行需要的最少移动步数。
二、方案：
实验环境：Windows 10，vs2019
解题思路：
n 个 x ，y 坐标分别放在 x[N]和 y[N] 数组里面，要求移动最少距离，
先假设所有坐标在 y 轴上，分析 y 轴上移动的最小距离：根据题目要求，
y[0...n-1] 移动后会变成相同的值， y 轴移动距离最小，则最后 y 轴所对应的值
是 y[(n+1)/2-1] ，即向中位数移动；
再假设所有坐标在 x 轴上，分析 x 轴上移动的最小距离：与 y 轴不同的
是， x[0...n-1] 移动后变成（位置）相邻间隔为 1 的 n 个连续的数组，为了使
移动距离最小，对 x[N] 进行第一次排序（从小到大排），较小的值 x[i] 移动后
对应的 x 坐标也较小，那么可以把 x[0...n-1] 的有序数组分别减去 n 个自然数。
x[0...n-1] ，如果都向一个值移动，便会变成相邻间隔为 1 的 n 个连续的数组，
所以之后的处理方式，则与 y 轴一样， x[0...n-1] 向中位数移动，便求出 x 轴
移动距离最小。
时间效率 O（nlogn）
空间效率 O（nlogn）
伪代码
//在满足所有网格只有一个士兵情况下，士兵们要以最少的总移动步数移动
成一个水平队列。
//输入：士兵数 C[1..n],位置 x[1..n],y[1...n]
资源评论
