小易老師是非常嚴厲的,它會要求所有學生在進入教室前都排成一列,并且他要求學生按照身高不遞減的順序排列。有一次,n個學生在列隊的時候,小易老師正好去衛生間了。學生們終于有機會反擊了,于是學生們決定來一次瘋狂的隊列,他們定義一個隊列的瘋狂值為每對相鄰排列學生身高差的絕對值總和。由于按照身高順序排列的隊列的瘋狂值是最小的,他們當然決定按照瘋狂值最大的順序來進行列隊?，F在給出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
輸出

100

解析：該題目放的規律比較明顯，要想獲得最大的瘋狂值，先給數組排序，然后把最大的放中間，兩邊放最小的，然后兩邊放次大的，然后兩邊再放次小的…

import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Scanner;public class Main {//5 10 25 25 40//25-10-40-5-25public static int getMaxCrazy(int []arr,int n){Arrays.sort(arr);LinkedList<Integer> queue = new LinkedList<>();queue.add(arr[n-1]);int low=0;int high=n-2;int count=n-1;//剩余需要取得數int index=0;//奇偶交替放大小的數if((n-1)%2==0){//剩余的數是偶數個for(int i=0;i<(n-1)/2;i++){if(index%2==0){//取最小的兩個數int min1 =arr[low++];int min2=arr[low++];int first=queue.getFirst();int last =queue.getLast();int sum1=Math.abs(first-min1)+Math.abs(last-min2);int sum2=Math.abs(first-min2)+Math.abs(last-min1);if(sum1>sum2){queue.addFirst(min1);queue.addLast(min2);}else{queue.addFirst(min2);queue.addLast(min1);}index++;}else{//取兩個次大的數int max1 =arr[high--];int max2=arr[high--];int first=queue.getFirst();int last =queue.getLast();int sum1=Math.abs(first-max1)+Math.abs(last-max2);int sum2=Math.abs(first-max2)+Math.abs(last-max1);if(sum1>sum2){queue.addFirst(max1);queue.addLast(max2);}else{queue.addFirst(max2);queue.addLast(max1);}index++;}}}else{//count=3//5 10 25 40//25-10-40-5for(int i=0;i<(n-1)/2+1;i++){if(index%2==0){//取小的數if(count-2>=0){//一次放兩個int min1 =arr[low++];int min2=arr[low++];int first=queue.getFirst();int last =queue.getLast();int sum1=Math.abs(first-min1)+Math.abs(last-min2);int sum2=Math.abs(first-min2)+Math.abs(last-min1);if(sum1>sum2){queue.addFirst(min1);queue.addLast(min2);}else{queue.addFirst(min2);queue.addLast(min1);}index++;count-=2;}else{//一次放一個int min1 =arr[low++];int first=queue.getFirst();int last =queue.getLast();int sum1=Math.abs(first-min1);int sum2=Math.abs(last-min1);if(sum1>sum2){queue.addFirst(min1);}else{queue.addLast(min1);}index++;count-=1;}}else{if(count-2>=0){//一次放兩個int max1 =arr[high--];int max2=arr[high--];int first=queue.getFirst();int last =queue.getLast();int sum1=Math.abs(first-max1)+Math.abs(last-max2);int sum2=Math.abs(first-max2)+Math.abs(last-max1);if(sum1>sum2){queue.addFirst(max1);queue.addLast(max2);}else{queue.addFirst(max2);queue.addLast(max1);}index++;count-=2;}else{//一次放一個int max1 =arr[high--];int first=queue.getFirst();int last =queue.getLast();int sum1=Math.abs(first-max1);int sum2=Math.abs(last-max1);if(sum1>sum2){queue.addFirst(max1);}else{queue.addLast(max1);}index++;count-=1;}}}}List<Integer> list = new ArrayList<>(queue);int max=0;for(int i=1;i<list.size();i++){max+=Math.abs(list.get(i)-list.get(i-1));}int temp=queue.pop();//需要檢測隊首的元素放在隊尾的情況，不然只能通過90%queue.addLast(temp);list = new ArrayList<>(queue);int max2=0;for(int i=1;i<list.size();i++){max2+=Math.abs(list.get(i)-list.get(i-1));}return Math.max(max, max2);}public static void main(String[] args) {Scanner sc = new Scanner(System.in);while(sc.hasNextLine()){int n =sc.nextInt();int [] arr= new int[n];for(int i=0;i<n;i++){arr[i]=sc.nextInt();}System.out.println(getMaxCrazy(arr, n));}}}

總結

以上是生活随笔為你收集整理的《网易编程题》疯狂队列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。