问题描述
有x轴上分布着n个石子,用list表示它们的位置,任务是把这些石子移动到1, 3, 5, 7, 2n-1或者2, 4, 6, 8, 2n位置。换句话说,这些石子要么全部移动到奇数位,要么全部移动到偶数位,返回最少的移动次数。每次智能移动1个石子,且每次只能移动一个单位,同一位置不能同时有2个石子。
示例
对于石子序列 [5, 4, 1] ,只需将4移动一步到3,输出为 1 ;而对于 [1, 6, 7, 8, 9] 而言,最优的移动方式为将1移动到2,将6移动到4,将7移动到6,将9移动到10,所以输出为 5 。
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
def moving_stones(list_stone): # 输入为包含石子位置的list x = 0 y = 0 list_stone.sort() for i in range(len(list_stone)): n = abs(list_stone[i] - 2*(i+1)+1) m = abs(list_stone[i] - 2*(i+1)) x += n y += m if x > y: return y else: return x li = [5, 4, 1] print('输入数组:', li) print('输出最小移动步数:', moving_stones(li)) |
运行结果
1 2 |
输入数组: [5, 4, 1] 输出最小移动步数: 1 |