首页 > 试题广场 >

疯狂队列

[编程题]疯狂队列

热度指数：19400 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小易老师是非常严厉的,它会要求所有学生在进入教室前都排成一列,并且他要求学生按照身高不递减的顺序排列。有一次,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

输出

算法知识视频讲解

Python

兜兜里有橙子

n = int(input())
x = list(map(int,input().split()))
x.sort()
i = len(x) - 1
j = 0
c = 0
while i - j >= 3:
    c += 2*x[i] - x[j] - x[j+1]
    i -= 1
    j += 1
if i - j == 2:
    c += x[i] - x[j]
c += max(x[i] - x[i-1], x[i] - x[0])
print(c)

编辑于 2019-07-30 14:44:20 回复(0)

Python

Lishion

逆向排序，分成较大部分和较小部分。再分奇偶讨论即可。

import math
def solve(nums):
    if len(nums) == 1: return nums[0]
    nums = sorted(nums, reverse=True)
    length = len(nums)
    max_part = nums[0: math.ceil(length / 2)]
    min_part = nums[math.ceil(length / 2):]
    if len(nums) % 2 == 0:
        return 2 * sum(max_part[:-1]) + max_part[-1] - 2 * sum(min_part[1:]) - min_part[0]
    else:
        return 2 * sum(max_part[:-2]) + max_part[-2] + max_part[-1] - 2 * sum(min_part)

编辑于 2019-06-23 20:06:11 回复(0)

Python

DeepMachine

本人认为最清晰，最好懂，最直白的讲解了😂😁
运行时间：27ms

占用内存：3568k

""""
思路:先将height排序，每一次取出最小值和最大值放在队列中
     然后再取出最小值和最大值,最小值放在上次最大值的右边
     最大值放在上次最小值的左边
     Note：需要判断输入个数的奇偶性，若是奇数，最后一个元素
     是防止在队头或者队尾，需要和当前的队头和队尾元素比较
eg1: 25-10-40-5-25(n为奇数)
    sort:5-10-25-25-40
    第一次取出min=5,max=40  queue:[5,40]
    第二次取出min=10,max=25 queue:[25,5,40,10]
    第三次取出25,放在队头or队尾？明显放在队尾差异更大 queue:[25,5,40,10,25]
    res = 20+35+30+15=100
eg2：1-2-4-8-6-10(n为偶数)
    sort:1-2-4-6-8-10
    第一次取出min=1,max=10 queue:[1,10]
    第一次取出min=2,max=8 queue:[8,1,10,2]
    第一次取出min=4,max=6 queue:[4,8,1,10,2,6]
    res = 4+7+9+8+4=32
    
"""
n = int(input())
height = list(map(int,input().split()))
height.sort()
min_value = height[0]
max_value = height[-1]
res = abs(max_value-min_value)
# 队头指针
top = 1
# 队尾指针
rear = n-2
while top<=rear:
    # 当n为奇数时，最后一步top==rear
    if top==rear:
        res += max(abs(min_value-height[top]),abs(max_value-height[rear]))
    else:
        # 计算右边差距
        res += abs(max_value-height[top])
        # 计算左边差距
        res += abs(min_value-height[rear])
        # update min and max
        min_value = height[top]
        max_value = height[rear]
    # 移动指针
    top += 1
    rear -=1
print(res)

发表于 2019-05-04 21:05:07 回复(2)

Python

稳扎稳打的🐖

n = int(input())
ls = [int(i) for i in input().split()]
ls.sort()
a = []

if len(ls) % 2 == 0:
    count = 1
    for i in range(len(ls)//2):
        maxNum, minNum = ls.pop(-1), ls.pop(0)
        if count > 0:
            a.append(maxNum)
            a.insert(0, minNum)
        else:
            a.append(minNum)
            a.insert(0, maxNum)
        count = -count

    sum = 0
    for j in range(len(a)-1):
        sum += abs(a[j]-a[j+1])
    print(sum)
else:
    count = 1
    for i in range(len(ls)//2):
        maxNum, minNum = ls.pop(-1), ls.pop(0)
        if count > 0:
            a.append(maxNum)
            a.insert(0, minNum)
        else:
            a.append(minNum)
            a.insert(0, maxNum)
        count = -count
    a1 = a[:]
    a1.append(ls[0])
    a2 = a[:]
    a2.insert(0, ls[0])

    sum1 = 0
    for j in range(len(a1)-1):
        sum1 += abs(a1[j]-a1[j+1])
    sum2 = 0
    for k in range(len(a2)-1):
        sum2 += abs(a2[k]-a2[k+1])
    print(max(sum1, sum2))

发表于 2019-04-17 10:50:35 回复(0)

Python

Ponder_xu

n=int(input())
s=list(map(int,input().split()))
ss=[]
if(n<=1):
print(0)
idx=1
while(len(s)>1): #当n是偶数时这样循环就好
m=max(s)
n=min(s)
if(idx==1): #第奇数次小的在前面
ss.append(m)
ss.insert(0,n)
idx=0
else: #第偶数次大的在前面
ss.append(n)
ss.insert(0,m)
idx=1
s.remove(m)
s.remove(n)
if(len(s)==1): #当n是奇数，最后一个数要挑下位置，放在第一个还是最后一个
if(abs(s[0]-ss[0])>abs(s[0]-ss[-1])):
ss.insert(0,s[0])
else:
ss.append(s[0])
sum=0
for i in range(len(ss)-1):
sum+=abs(ss[i]-ss[i+1])

print(sum)

发表于 2019-04-11 11:26:00 回复(0)

Python

Re:煙花ゼロから易冷

n = int(input())
h = list(map(int, input().split()))
h.sort()
temp = [h[0]]
crazy_sum = 0
left = 1
right = n-1
while left <= right:
    hl_0 = abs( h[left] - temp[0] )
    hl__1 = abs( h[left] - temp[-1] )
    hr_0 = abs( h[right] - temp[0] )
    hr__1 = abs( h[right] - temp[-1] )
    index = [hl_0, hl__1, hr_0, hr__1]
    max_index = max(index)
    if index.index(max_index) == 0:
        temp.insert(0, h[left])
        left += 1
    elif index.index(max_index) == 1:
        temp.append(h[left])
        left += 1
    elif index.index(max_index) == 2:
        temp.insert(0, h[right])
        right -= 1
    else:
        temp.append(h[right])
        right -= 1
for i in range(n-1):
    crazy_sum += abs(temp[i] - temp[i+1])
print(crazy_sum)

发表于 2019-04-02 17:18:15 回复(0)

Python

Working_CC

#这个题的排列方式是固定的，大数中间插小数，大数小的放两边，小数大的放一边，根据数列大小的奇偶性，使用不同算法。
import sys
if __name__=='__main__':
    line=sys.stdin.readline().strip()
    num=int(line)
    line1=sys.stdin.readline().strip()
    num_list=list(map(int,line1.split()))
    num_list=sorted(num_list)
    a=num//2
    l_list=num_list[a:]
    s_list=num_list[:a]

    if num%2!=0:
        ans=sum(l_list)+sum(l_list[2:])-2*sum(s_list)
    else:
        ans=sum(l_list)+sum(l_list[1:])-sum(s_list)-sum(s_list[:-1])
    print (ans)

编辑于 2019-03-31 16:30:14 回复(0)

Python

丶昕楚

Python Solution

while True:
    try:
        n=int(input())
        h=sorted(list(map(int,input().split())))
        Max,Min,res=0,0,0
        if n%2==1:
            while(len(h)>1):
                res+=h[-1]-Min+Max-h[0]
                Min=h.pop(0)
                Max=h.pop(-1)
            res+=max(abs(h[0]-Min),abs(h[0]-Max))
            print(res)
        else:
            while(len(h)>0):
                res+=h[-1]-Min+Max-h[0]
                Min=h.pop(0)
                Max=h.pop(-1)
            print(res)
    except:
        break

发表于 2019-03-20 19:52:22 回复(0)

Python

十月_13

n = int(input())
x = list(map(int, input().split()))
x.sort()
mid = n//2 a = []
b = []
head = 0 last = n-1 a.append(x[mid]) for i in range(0, mid):
    a.append(x[head])
    a.append(x[last])
    head+=1  last-=1 for i in range(0,n-1):
    all = abs(a[i] - a[i+1])
    b.append(all) print(sum(b))

发表于 2019-03-18 20:54:25 回复(0)

Python

我要扛offer回家

n=int(input())
h=list(map(int,input().split()))
h.sort()
tmp=[h[0]]
left=1
right=n-1
sum=0
while left<=right:
    l0=abs(h[left]-tmp[0])
    l1=abs(h[left]-tmp[-1])
    r0=abs(h[right]-tmp[0])
    r1=abs(h[right]-tmp[-1])
    t=max(l0,l1,r0,r1)
    if t==l0:
        tmp.insert(0,h[left])
        left+=1
    elif t==l1:
        tmp.append(h[left])
        left+=1
    elif t==r0:
        tmp.insert(0,h[right])
        right-=1
    else:
        tmp.append(h[right])
        right-=1
for i in range(n-1):
    diff=abs(tmp[i+1]-tmp[i])
    sum=sum+diff
print(sum)

发表于 2019-03-17 20:10:27 回复(0)

Python

佛祖菩萨保佑我顺顺利利升级加薪

通过60%哪里出错了呢
n = int(input())
l = list(map(int, input().split()))
mid = max(l)
tmp = [mid]
l.remove(mid) def fin2min(list):
    min_1 = min(l)
    tmp.append(min_1)
    l.remove(min_1)
    min_2 = min(l)
    tmp.insert(0, min_2)
    l.remove(min_2) return tmp def fin2max(list):
    max_1 = max(l)
    tmp.append(max_1)
    l.remove(max_1)
    max_2 = max(l)
    tmp.insert(0, max_2)
    l.remove(max_2) return tmp while len(l) >= 2:
    fin2min(l)
    fin2max(l) if len(l) == 1: if abs(l[0]-tmp[0])>=abs(l[0]-tmp[-1]):
        tmp.insert(0,l[0]) else:
        tmp.append(l[0])
sum = 0 for i in range(n-1):
    sum += abs(tmp[i+1]-tmp[i]) print(sum)

发表于 2019-03-17 13:44:31 回复(0)

Python

l一人在山旁l

 自己写的代码，超级简单，思路是先加一个大的，再一左一右各加一个小的，
 再一左一右各加一个大的，一直到剩最后一个判断一下哪里比较合适。最后计算结果。

n = int(input())
a = [int(i) for i in input().split()]
a.sort()
b = []
flag = 0
b.append(a[-1])
a.pop()
while a:
    if flag==0:
        if a:
            b.append(a[0])
            a.pop(0)
        if a:
            b.insert(0,a[0])
            a.pop(0)
        flag=1
    else:
        if a:
            b.append(a[-1])
            a.pop()
        if a:
            b.insert(0,a[-1])
            a.pop()
        flag=0

if len(b)>=2 and abs(b[0]-b[1])<abs(b[0]-b[-1]):
    x = b.pop(0)
    b.append(x)

s_sum = 0

for i in range(len(b)-1):
    s_sum+=abs(b[i]-b[i+1])

print(s_sum)
#print(b)

发表于 2019-02-10 15:52:35 回复(1)

Python

liusai_1992

#/usr/bin/env pyhton

#-*- coding:utf-8 -*-

'疯狂队列'

__author__ = 'Liusai'

‘’‘

代码是自己写的，想了好久要不要用分奇偶的方法，后来写了下还是分就比较直观，

主要有两点：1.对于最终拍成的疯狂队列ABABABABABABAB。。。。，某一个人对最终疯狂值的影响只与所站的位置为A类还是B类有关，与具体是哪个A或者B无关（首末除外）2.如果队列的疯狂值再加上

首末两人的疯狂值的差，其总和保持不变（与A、B两个类别中的元素具体怎么排列无关），最后用综合减去首末两项的差值就能得到最终的疯狂值了

’‘’

lenth = int(raw_input(''))

h = map(int,raw_input('').split())

h = sorted(h)

if lenth % 2 == 0:

h1 = h[:lenth/2]

h2 = h[lenth/2:]

result = 2 * sum(h2) - 2 * sum(h1)

result -= h2[0] - h1[-1]

else:

h1 = h[ : ( lenth - 1 ) / 2 ]

h2 = h[ ( lenth + 1) / 2 : ]

result = 2 * sum(h2) - 2 * sum(h1)

result -= min((h[(lenth-1)/2] - h1[-1]),(h2[0]-h[(lenth-1)/2]))

print result

发表于 2017-08-23 17:08:58 回复(3)

Python

袋鼠和考拉

import sys

if __name__ == "__main__":
    n = int(sys.stdin.readline().strip())
    line = sys.stdin.readline().strip()
    x = map(int, line.split())
    if n%2 == 0:
        x = sorted(x)
        ans = abs(x[0] - x[-1])
        for i in range(n/2-1):
            ans = ans + abs(x[i]-x[-i-2]) + abs(x[-i-1]-x[i+1])
    if n%2 == 1:
        if (n/2)%2 == 0:
            x = sorted(x,reverse=True)
            ans1 = abs(x[-1]-x[0]) + abs(x[-1]-x[1])
            for i in range((n-1)/2+1)[2:]:
                ans1 = ans1 + abs(x[-i]-x[i-2]) + abs(x[-i]-x[i])
            x = sorted(x)
            ans2 = abs(x[-1]-x[0]) + abs(x[-1]-x[1])
            for i in range((n-1)/2+1)[2:]:
                ans2 = ans2 + abs(x[-i]-x[i-2]) + abs(x[-i]-x[i])
            ans = max(ans1,ans2)
        if (n/2)%2 == 1:
            x = sorted(x)
            ans1 = abs(x[0]-x[-1]) + abs(x[0]-x[-2])
            for i in range((n-1)/2)[1:]:
                ans1 = ans1 + abs(x[i]-x[-i-2]) + abs(x[i]-x[-i])
            x = sorted(x,reverse=True)
            ans2 = abs(x[0]-x[-1]) + abs(x[0]-x[-2])
            for i in range((n-1)/2)[1:]:
                ans2 = ans2 + abs(x[i]-x[-i-2]) + abs(x[i]-x[-i])
            ans = max(ans1,ans2)
    print ans

发表于 2017-08-15 10:31:21 回复(0)

Python

阿里内推小哥

贴一个完美python版的，不用考虑奇偶和其他乱七八糟的也是先排序得到 l，设一个空列表temp=[l[0]]，即把最小值放第一个，初始状况left=1指向第二个，right=n-1指向最后一个，然后分四种情况，分别是l[left]和temp[0],l[left]和temp[-1],l[right]和temp[0],l[right]和temp[-1]比较，取差的绝对值最大的一组加进temp，如何是取到了left，就把left右移，取到right，就把right左移，直到left>right为止,最后在temp里求差（也可以在不用这一步，不过能说的清晰一些）

n = int(input())
l = list(map(int,input().split()))

l.sort()
temp =[l[0]]
left = 1
right = n-1
res = 0
while left<=right:
    r0 = abs(temp[0] - l[right])
    lr = abs(temp[-1] - l[right])
    l0 = abs(temp[0]-l[left])
    l1 = abs(temp[-1]-l[left])
    tl = [r0,lr,l0,l1]
    m = max(tl)
    if tl.index(m)==0:
        temp.insert(0,l[right])
        right-=1
    if tl.index(m)==1:
        temp.append(l[right])
        right-=1
    if tl.index(m)==2:
        temp.insert(0,l[left])
        left+=1
    if tl.index(m)==3:
        temp.append(l[left])
        left+=1


for i in range(n-1):
    res+=abs(temp[i+1]-temp[i])
print(res)

编辑于 2017-08-13 21:01:03 回复(1)

Python

billie

# python代码，下午一直通不过，现在通过了
# 跟楼上的思路一样，剩两个数的时候，情况没考虑清楚就一直过不了
n = int(input())
nums = [int(k) for k in input().split()]
nums = sorted(nums)
result = []
result.append(nums[-1])
nums.pop()
while len(nums):
    result.append(nums[0])
    result.insert(0, nums[1])
    result.append(nums[-1])
    result.insert(0, nums[-2])
    nums.pop()
    nums.pop()
    nums.pop(0)
    nums.pop(0)
    if len(nums) < 4:
        break
if len(nums) == 3:
    result.append(nums[0])
    result.append(nums[2])
    result.insert(0, nums[1])
elif len(nums) == 2:
    if abs(result[0] - nums[0]) + abs(result[-1] - nums[1]) > abs(result[0] - nums[1]) + abs(result[-1] - nums[0]):
        result.append(nums[1])
        result.insert(0, nums[0])
    elif abs(result[0] - nums[0]) + abs(result[-1] - nums[1]) == abs(result[0] - nums[1]) + abs(result[-1] - nums[0]):
        result.append(nums[0])
        result.append(nums[1])
    else:
        result.append(nums[0])
        result.insert(0, nums[1])
elif len(nums) == 1:
    if abs(result[-1] - nums[0]) > abs(result[0] - nums[0]):
        result.append(nums[0])
    else:
        result.insert(0, nums[0])
re = 0
for i in range(n - 1):
    re += abs(result[i] - result[i + 1])
print(re)

发表于 2017-08-12 22:17:27 回复(0)