题目:序列重排-求相邻差和最大
分析:数学题,分析 找规律
来源:京东笔试题(2021-9-12)
''' 题目:序列重排 给一个长度为n的序列A,你可以将序列中的元素按任意顺序重新排列,请你找到一种排列方式使得相邻两个数的差值之和最大,输出该最大值。 即若重拍后的序列是B,你需要使 |B1-B2|+|B2-B3|+···+|Bn-1-Bn|的值最大 例: 输入 输出 8 3 5 1 5 输入 输出 8 5 5 2 2 2 1 分析: 先按照升序排序!!! 例 1 2 3 4 5 1 2 3 5 3 5 4 3 5 1 2 1 2 排序后的序列B 一定 满足 高低高低的这种排列方式如上例所示 对于 1 2 5 从左边分析可以看到, 可以重写为: 5 - 1 5 - 2 1 2 被减了两遍 -1 -1 - 2 - 2 3 - 1 5 被加了两遍 +5 +5 4 - 2 3 4 在两边 各被加了一遍 +4 +4 +3 +3 -4 -3 对于 1 2 3 5 分析可知 5 - 1 5 - 2 1 被减了两遍 -1 -1 3 - 1 5 被加了两遍 +5 +5 2 3 在两边分别被减了、加了一遍 -2 -2 +3 +3 +2 -3 综上所述,可以将数组进行排序, 如果数组元素为奇数个:前边n/2个元素(low),后边n/2+1个元素(high) (sum(high)-sum(low))*2 - high[0]-high[1] (当个数是奇数时,让high中比较小的值在两边) 如果数组元素为偶数个:前边n/2个元素(low),后边n/2个元素(high) (sum(high-sum(low)))*2 - high[0] + low[-1] (当个数是偶数时,让high中比较小的值在第一个,low中比较大的值在最后一个) ''' def getMax(nums): nums.sort() mid = len(nums) // 2 low, high = nums[:mid], nums[mid:] if len(nums) % 2 != 0: return (sum(high) - sum(low)) * 2 - high[0] - high[1] else: return (sum(high) - sum(low)) * 2 - high[0] + low[-1] nums = list(map(int, input().strip().split())) print(getMax(nums))