牛家莊幼稚園為慶祝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.util.Arrays;
import java.util.Scanner;
/*
* 考慮我們已經将身高升序排序了,然後對于前k個小朋友組成隊形的身高差的最大值的最小值為f(k),
* 并且第k個和第(k-1)個小朋友是相鄰的。現在我們加入第(k+1)個小朋友,
* 考慮到第(k + 1)個小朋友身高是大于等于前面的小朋友,
* 插入隊形之後,第(k + 1)個小朋友一定與兩個小朋友相鄰,
* 是以當我們将第(k + 1)個小朋友插入到第k個和第(k - 1)個小朋友中間可以得到f(k + 1)
* 的下界一定是max(f(k), h[k] - k[k - 2]),
* 我們又注意到這樣插入之後第(k + 1)個和第k個小朋友還是相鄰的,于是這樣可以一直推廣下去。
* 考慮最初3個小朋友的時候這樣也是可行的, 于是問題變成了求max(h[i] - h[i - 2])。
*/
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[] num = new int[N];
for(int i = 0 ; i < N ; i++){
num[i] = in.nextInt();
}
Arrays.sort(num);
int min = 0;
for(int i = 2 ; i < N ; i++){
min = Math.max(min,num[i]-num[i-2]);
}
System.out.print(min);
in.close();
}
} 複制
