牛家庄幼儿园为庆祝61儿童节举办庆祝活动,庆祝活动中有一个节目是小朋友们围成一个圆圈跳舞。牛老师挑选出n个小朋友参与跳舞节目,已知每个小朋友的身高h_i。为了让舞蹈看起来和谐,牛老师需要让跳舞的圆圈队形中相邻小朋友的身高差的最大值最小,牛老师犯了难,希望你能帮帮他。
如样例所示:
当圆圈队伍按照100,98,103,105顺时针排列的时候最大身高差为5,其他排列不会得到更优的解
输入包括两行,第一行为一个正整数n(3 ≤ n ≤ 20) 第二行为n个整数h_i(80 ≤ h_i ≤ 140),表示每个小朋友的身高。
输出一个整数,表示满足条件下的相邻小朋友身高差的最大值。
4 100 103 98 105
5
import java.math.BigInteger; import java.util.Arrays; import java.util.Scanner; //System.out.println(""); public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int d=0; int dm=0; int n = sc.nextInt(); int[] array = new int[n]; for(int i=0; i<n; i++){ array[i] = sc.nextInt(); } Arrays.sort(array);//身高排序 for(int i=2;i<n;i+=2){ d=array[i]-array[i-2]; if(d<0)d=-d; if(d>=dm)dm=d; }//dm为第一列最大身高差 for(int i=3;i<n;i+=2){ d=array[i]-array[i-2]; if(d<0)d=-d; if(d>=dm)dm=d; }//dm为第一列和第二列 最大身高差 d=array[0]-array[1]; if(d<0)d=-d; if(d>=dm)dm=d; d=array[n-1]-array[n-2]; if(d<0)d=-d; if(d>=dm)dm=d; //dm为第一列、第二列 、列连接处 最大身高差 System.out.println(dm); } }思路:假如h1 h2 h3 h4 h5 h6 ..hn 依次递增(排序)h1 h2h3 h4h5 h6...hn-1 hn这样形成的圈可以保证身高差的最大值最小。 依次计算 身高差 d 取最大值即可