首页 > 试题广场 >

国际交流会

[编程题]国际交流会

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

最近小强主办了一场国际交流会，大家在会上以一个圆桌围坐在一起。由于大会的目的就是让不同国家的人感受一下不同的异域气息，为了更好地达到这个目的，小强希望最大化邻座两人之间的差异程度和。为此，他找到了你，希望你能给他安排一下座位，达到邻座之间的差异之和最大。

输入描述:

输入总共两行。
第一行一个正整数，代表参加国际交流会的人数(即圆桌上所坐的总人数，不单独对牛牛进行区分）
第二行包含个正整数，第个正整数代表第个人的特征值。
其中
注意：
邻座的定义为: 第人的邻座为，第人的邻座是，第人的邻座是。
邻座的差异值计算方法为。
每对邻座差异值只计算一次。

输出描述:

输出总共两行。
第一行输出最大的差异值。
第二行输出用空格隔开的个数，为重新排列过的特征值。
（注意：不输出编号）
如果最大差异值情况下有多组解，输出任意一组即可。

示例1

输入

4
3 6 2 9

输出

20
6 2 9 3

说明

这么坐的话
差异和为为最大的情况。

算法知识视频讲解

Java

霸王龙v2

将数组排序，利用双指针从头和尾依次选取最大和最小值存在为结果数组中，再求最大差值。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }
        Arrays.sort(nums);
        long maxSum = 0;
        int[] result = new int[n];
        int i = 0, j = n - 1, idx = 0;
        while (i < j) {
            result[idx++] = nums[i++];
            result[idx++] = nums[j--];
        }
        if (n % 2 == 1)
            result[idx] = nums[i];
        for (i = 1; i < n; i++) {
            maxSum += Math.abs(result[i] - result[i - 1]);
        }
        maxSum += Math.abs(result[0] - result[n - 1]);
        System.out.println(maxSum);
        for (int r : result) {
            System.out.print(r + " ");
        }
    }
}

发表于 2022-07-10 11:23:41 回复(0)