[Algorithm] 🌴白駿11497丸木を飛び越える

0、問題

南圭は丸太を立てて飛び越えるのが好きだ.だからN個の丸い木を円形に立てて、それから踊って遊びたいです.南圭は隣接する丸木を円形で飛び越え、この場合、各隣接する丸木の高さ差が最小になる.
丸木を飛び越える難易度は隣接する2つの丸木の間の高さ差の最値によって決まる.高い{2,4,5,7,9}丸い木を建てると仮定します.これを[2,9,7,4,5]の順序で確立すると、最初の丸木と最後の丸木も隣接している.すなわち、高さ2のものと高さ5のものも隣接している.配列[2,9,7,4,5]の難易度は|2−9|=7であった.より良い配列[2,5,9,7,4]を作成することができ,この配列の難易度は|5−9|=4である.難易度がこれより低い配列を作ることができないため、この配列は南圭が探している答えになるだろう.
入力
入力はT個の試験用例からなる.最初の行はTを与える.次の各行において、第1行は丸木個数を表す整数N(5≦N≦10000)を与え、第2行は丸木高さを表す整数Lを与える.(1 ≤ Li ≤ 100,000)
しゅつりょく
各試験例では、所与の原木の行が達成できる最小難易度を出力する.

1.アイデア

💡 昇順で数値列を並べます
💡 小さな数字から(1,n),(2,n−1),...新しいアレイを作成するために交互に配置
💡 新しい配列の隣接する数値の違いを比較することで、最大の数値を出力します.

2.コア解答

1)昇順で数字列を並べる

Arrays.sort(arr);

2)小さな数字から(1,n),(2,n−1),...新しいアレイを作成するために交互に配置

for(int i=0, j=0; j<n/2; i=i+2, j++) {
				wood[j] = arr[i];
				wood[n-j-1] = arr[i+1];
			}
			
if(n % 2 == 1)
				wood[n/2] = arr[n-1];

3)新規配列の隣接数の差を比較し、最大数を出力する

int max = Math.abs(wood[0]-wood[n-1]);
for(int i=1; i<n; i++) 
			max = Math.max(max,Math.abs(wood[i]-wood[i-1]));

3.コード

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Greedy_13 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(br.readLine());
		
		while(tc-- > 0) {
			int n = Integer.parseInt(br.readLine());
			int arr[] = new int[n];
			int wood[] = new int[n];
			
			String s[] = br.readLine().split(" ");
			
			for(int i=0; i<n; i++)
				arr[i] = Integer.parseInt(s[i]);
			
			Arrays.sort(arr);
			
			for(int i=0, j=0; j<n/2; i=i+2, j++) {
				wood[j] = arr[i];
				wood[n-j-1] = arr[i+1];
			}
			
			if(n % 2 == 1)
				wood[n/2] = arr[n-1];
			
			int max = Math.abs(wood[0]-wood[n-1]);
			for(int i=1; i<n; i++) 
				max = Math.max(max,Math.abs(wood[i]-wood[i-1]));
			
			System.out.println(max);
		}
	}

}

4.結果

成功
(最終値が初期値に隣接していることを考慮する必要があります!)