HDOJ(HDU)2523 SORT AGAIN(導出ソート、、)


Problem DescriptionはあなたにN個の整数をあげて、x 1,x 2...xn、2つの整数の組み合わせを取って|xi-xj|,(0Input入力データは、まず、C群を含む試験例を示す正の整数Cを含む.各試験データのセットの最初の行は2つの整数N,Kを含む.(1OutputテストデータのセットごとにK番目の組み合わせ数を出力し、各出力インスタンスが1行を占めます.
Sample Input 3 3 2 4 0 7 4 2 1 2 3 4 2 1 2 9
Sample Output 4 2 7
題意はとても簡単です~第k個の組み合わせの数を求めます(組み合わせの数は小さい時から並べ替えて、繰り返しの数は一回だけ計算します)
分かりやすくて、n個の数の組み合わせの数は最大でn*(n-1)/2個あって、重複することがあるかもしれなくて、このn*(n-1)/2個の組み合わせの数を配列で記憶して、小さいから大きいまで並べ替えて、更に小さいから大きいまでk番目の重複しない数を探し出します!!!

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t =sc.nextInt();

        while(t-->0){
            int n =sc.nextInt();
            int k=sc.nextInt();
            int a[] = new int[n];
            for(int i=0;i<n;i++){
                a[i]=sc.nextInt();
            }
            Arrays.sort(a);
            int b[] = new int[n*(n-1)/2];
            int h=0;
            for(int i=0;i<n-1;i++){
                for(int j=i+1;j<n;j++){
                    b[h]=Math.abs((a[i]-a[j]));
                    h++;
                }
            }

            Arrays.sort(b);
            h=0;
            for(int i=0;i<b.length-1;i++){
                if(b[i]!=b[i+1]){
                    h++;
                    if(h==k){
                        h=i;
                        break;
                    }
                }
            }
            System.out.println(b[h]);
        }
    }
}