Chia cặp

Submit solution
Points: 1
Time limit: 1.0s
Memory limit: 977M
Author:
Giang_CNTT3_K60
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Cho n học sinh có năng lực a1, a2,..., an. Thầy giáo muốn chọn ra k nhóm học sinh rời nhau mỗi nhóm có đúng 2 bạn để tham gia cuộc thi. Để cân đối thầy muốn ghép những bạn có năng lực thấp với bạn có năng lực cao tức là chênh lệch năng lực của 2 bạn trong cùng nhóm càng lớn càng tốt. Sau khi ghép các nhóm thì k nhóm có k độ chênh lệch.

Hãy tìm cách chọn ra k nhóm sao cho độ chênh lệch của nhóm nhỏ nhất là lớn nhất hãy xuất ra giá trị đó.

Input

Dòng đầu có 2 số nguyên n,k \((2≤n≤3×10^5,1≤k≤n/2)\).

Dòng thứ hai có n số nguyên a1,a2,...,an \((1≤a_i≤10^9)\)

Output

In ra một số nguyên là kết quả bài toán

Ví dụ

Input

6 2

1 4 3 7 12 9

Output

8

Comments


  • 0
    Hoan_CNTT_VA2_K61  commented on Oct. 25, 2021, 1:06 p.m.

    tham khảo ý tưởng:

    #include<bits/stdc++.h>
using namespace std;
int main(){
    int n, k, max=INT_MAX, d;
    cin >> n >> k;
    d = n-k;
    int a[n+5];
    for(int i=0;i<n;i++) cin >> a[i];
    sort(a, a+n);
    for(int i=0;i<k;i++){
        if(a[i+d]-a[i] < max) max = a[i+d]-a[i]; 
    }
    cout << max;
    return 0;
}