【2018校招真题】 疯狂队列（python）

题目描述

小易老师是非常严厉的,它会要求所有学生在进入教室前都排成一列,并且他要求学生按照身高不递减的顺序排列。有一次,n个学生在列队的时候,小易老师正好去卫生间了。学生们终于有机会反击了,于是学生们决定来一次疯狂的队列,他们定义一个队列的疯狂值为每对相邻排列学生身高差的绝对值总和。由于按照身高顺序排列的队列的疯狂值是最小的,他们当然决定按照疯狂值最大的顺序来进行列队。现在给出n个学生的身高,请计算出这些学生列队的最大可能的疯狂值。小易老师回来一定会气得半死。
输入描述:
输入包括两行,第一行一个整数n(1 ≤ n ≤ 50),表示学生的人数 第二行为n个整数h[i](1 ≤ h[i] ≤> 1000),表示每个学生的身高
输出描述:
输出一个整数,表示n个学生列队可以获得的最大的疯狂值。

如样例所示:
当队列排列顺序是: 25-10-40-5-25, 身高差绝对值的总和为15+30+35+20=100。 这是最大的疯狂值了。
示例1
输入
5
5 10 25 40 25
输出
100

解题思路
本题需要寻找最大的疯狂值，可以先求解疯狂队列，最后再计算疯狂值。
求解疯狂队列的方法为：在一个数组中间放入数组最大值，然后在两端依次放入两最小值、两最大值…
具体来说：
1、将数组排序后分为两部分，分别为l 和 r，并用result数组存入数组最大值；

nums.sort()
l = nums[0: length // 2]
r = nums[length // 2: length - 1]
result = [nums[length - 1]]

2、不断循环遍历l和r，若为奇数次遍历，则在result数组的前后插入两最小值，若为偶数次遍历，则在result数组的前后插入两最大值

i = 0 
while l or r:
    if i % 2== 0:
        if len(l) > 0:
            result.insert(0, l[0])
            l.remove(l[0])
        if len(l) > 0:
            result.append(l[0])
            l.remove(l[0])
        i += 1
    else:
        if len(r) > 0:
            result.insert(0, r[len(r) - 1])
            r.remove(r[len(r) - 1])
        if len(r) > 0:
            result.append(r[len(r) - 1])
            r.remove(r[len(r) - 1]) 
        i += 1

3、最后根据疯狂队列计算疯狂值即可：

r = 0
for i in range(1, len(result)):
    r += abs(result[i] - result[i - 1])
print(r)

完整代码

length = int(input())
nums = list(map(int, input().split()))

nums.sort()
l = nums[0: length // 2]
r = nums[length // 2: length - 1]
result = [nums[length - 1]]
i = 0 
while l or r:
    if i % 2== 0:
        if len(l) > 0:
            result.insert(0, l[0])
            l.remove(l[0])
        if len(l) > 0:
            result.append(l[0])
            l.remove(l[0])
        i += 1
    else:
        if len(r) > 0:
            result.insert(0, r[len(r) - 1])
            r.remove(r[len(r) - 1])
        if len(r) > 0:
            result.append(r[len(r) - 1])
            r.remove(r[len(r) - 1]) 
        i += 1
r = 0
for i in range(1, len(result)):
    r += abs(result[i] - result[i - 1])
print(r)