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番目の重複しない数を探し出します!!!
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]);
}
}
}