笔试-算法|【算法】2021-3-7字节跳动2022春招笔试第一场第二题（庆祝61）算法|贪心算法|字节跳动

我没投但是我同学投了，看了这个笔试题感觉挺有意思的，就写一下：

题目链接：https://www.nowcoder.com/questionTerminal/0c16f758949f4d17ab73a9a1ffe7ab9b
来源：牛客网
本题也是： 2017牛客网第四次全国模拟考试中的一题

题目

牛家庄幼儿园为庆祝61儿童节举办庆祝活动,庆祝活动中有一个节目是小朋友们围成一个圆圈跳舞。牛老师挑选出n个小朋友参与跳舞节目,已知每个小朋友的身高h_i。为了让舞蹈看起来和谐,牛老师需要让跳舞的圆圈队形中相邻小朋友的身高差的最大值最小,牛老师犯了难,希望你能帮帮他。
如样例所示:
当圆圈队伍按照100,98,103,105顺时针排列的时候最大身高差为5,其他排列不会得到更优的解

输入描述:

输入包括两行,第一行为一个正整数n(3 ≤ n ≤ 20) 第二行为n个整数h_i(80 ≤ h_i ≤ 140),表示每个小朋友的身高。

示例1

输入:
4
100 103 98 105
输出：
5

import java.util.*; 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排序 Arrays.sort(arr); int left = 0, right = n-1; int j = 0; int[] res = new int[n]; while(left < right){ res[left] = arr[j]; res[right] = arr[j+1]; left++; right--; j+=2; } if(n%2 != 0){ res[n/2] = arr[n-1]; } int max = Integer.MIN_VALUE; for(int k = 1; k < n; k++){ int temp = res[k]-res[k-1%n]; if(temp < 0){ temp = -temp; } if(temp > max){ max = temp; } } System.out.println(max); } }

思路：

要求要相邻两个的差最小，并且是环状，所以要考虑第一个和最后一个
此处将升序的数组交 arr ，符合题目要求的数组叫 res，以 arr的数组中第一个数为基准，把他放在res的第一个，在他的右边和左边（即res的最后一个数）分别放两个和他相差最少的数，他右边可以放arr[第二个数]，左边可以放arr[第三个数]，依次类推，从而形成这个排队过程：

起初arr 序列为： 1 2 3 4 5 6 7