首页 > 试题广场 >

疯狂队列

[编程题]疯狂队列

热度指数：209 时间限制：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

输出

算法知识视频讲解

白色高跟鞋

python10行解决：

def cal(nums):
    nums.sort()
    mid = len(nums) // 2
    if len(nums) & 1:
        less, great = nums[:mid], nums[mid + 1:]
        return 2 * (sum(great) - sum(less)) + nums[mid] - great[0]
    else:
        less, great = nums[:mid], nums[mid:]
        return 2 * (sum(great) - sum(less)) + less[-1] - great[0]

# ---IO--- #    
# input_n = int(input())
# input_nums = list(map(int, input().split()))
# print(cal(input_nums))

解析：https://blog.nowcoder.net/n/aee5c4e3c14f48eeb678c6f839a6369b

编辑于 2020-07-31 16:02:38 回复(0)

Python3

endersuu

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

nums.sort()
#print(nums)


if n % 2 == 0:
    sum2 = sum(nums[n//2+1:])
    #print(sum2)
    sum_2 = sum(nums[:n//2-1])
    #print(sum_2)
    sum1 = nums[n//2]
    #print(sum1)
    sum_1 = nums[n//2-1]
    #print(sum_1)



else:
    sum2 = sum(nums[n//2+2:])
    #print(sum2)
    sum_2 = sum(nums[:n//2])
    #print(sum_2)
    sum1 = sum(nums[n//2:n//2+2])
    #print(sum1)
    sum_1 = 0
    #print(sum_1)

print(sum2*2 - sum_2 *2 + sum1 - sum_1)

发表于 2021-09-19 02:44:10 回复(0)

tys16

双端队列java实现

import java.util.Scanner;

import java.util.LinkedList;
import java.util.Deque;
import java.util.Arrays;
import java.util.Collections;

public class Main{
    public static void main(String[] args){
Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        Deque<Integer> record = new LinkedList<>();
        record.offerFirst(arr[0]);
        record.offerLast(arr[n-1]);
        int i = 1, j = n-2, index = 1;
        while(i < j){
            if((index & 1) > 0){
                record.offerFirst(arr[j--]);
                record.offerLast(arr[i++]);
            }else{
                record.offerFirst(arr[i++]);
                record.offerLast(arr[j--]);
            }
            index++;
        }
        if(i == j){
            if(Math.abs(arr[i] - record.peekFirst()) >= Math.abs(arr[i] - record.peekLast())){
                record.offerFirst(arr[i]);
            }else{
                record.offerLast(arr[i]);
            }
        }
        int ans = 0;
        int pre = record.pollFirst();
        int cur = 0;
        while(!record.isEmpty()){
            cur = record.pollFirst();
            ans += Math.abs(cur - pre);
            pre = cur;
        }
        System.out.println(ans);
    }
}

发表于 2020-07-12 16:45:26 回复(0)

桃符

import java.util.Scanner;
import java.util.Arrays;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int arr[] = new int[n];
        for(int i = 0;i<n;i++){
            arr[i] = in.nextInt();
        }
        if(n==1) return;
        Arrays.sort(arr);
        int sum = 0 ;
        int i = 0,j=n-1;
        int left=0,right=0;
        boolean flag = true;
        while(j>i){
            if(flag){
                sum+=(left-arr[i])+(arr[j]-right);
                left =arr[i];
                right = arr[j];
                flag = false;
                i++;
                j--;
            }else{
                sum+=(arr[j]-left)+(right-arr[i]);
                left =arr[j];
                right = arr[i];
                flag =true;
                i++;
                j--;
            }
        }
        if(i==j){
            sum+=Math.max(Math.abs(left-arr[i]), Math.abs(right-arr[j]));
        }
        System.out.println(sum);
}
}

编辑于 2018-09-11 16:37:52 回复(0)