AMR10G.cpp

#include<iostream>
using namespace std;
 
const int MAX = 20005;
 
int N;              // Lần lượt là số lượng đứa trẻ
int K;              // Số lượng trẻ cần đóng vai binh lính
int Height[MAX];    // Mảng lưu chiều cao của N đứa trẻ
 
void Merge(int *height, int left, int m, int right)
{
    int l = left, r = m + 1, k = 0;
    int *temp = new int[right - left + 1];
 
    while(l <= m && r <= right)
    {
        if(height[l] > height[r]) temp[k++] = height[l++];
        else temp[k++] = height[r++];
    }
 
    while(l <= m) temp[k++] = height[l++];
 
    while(r <= right) temp[k++] = height[r++];
 
    for(int i = 0; i < k; i++)
        height[i + left] = temp[i];
 
    delete[] temp;
}
 
void MergeSort(int *height, int left, int right)
{
    int m;
    if(left < right)
    {
        m = (left + right)/2; 
        MergeSort(height, left, m);
        MergeSort(height, m + 1, right);
        Merge(height, left, m, right);
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
 
    // comment dòng này trước khi submit
    freopen("input.txt","r",stdin);
 
    int TC = 0;
    cin >> TC;
 
    for(int tc = 0; tc < TC; tc++)
    {
        cin >> N >> K;
        for(int i = 0; i < N; i++)
            cin >> Height[i];
 
        // Nếu chỉ phải chọn 1 đứa trẻ thì đáp án là 0
        if(K == 1) cout << "0" << endl;
        else
        {
            // Sắp xếp những đứa trẻ theo chiều cao giảm dần
            MergeSort(Height, 0, N-1);
 
            // Khi mảng đã sắp xếp, ta chỉ cần kiểm tra độ chênh lệnh
            // chiều cao giữa đứa trẻ thứ i và thứ i + K - 1
            // chọn ra khoảng nào có độ chênh lệnh nhỏ nhất sẽ là kết quả cần tìm
            int min = 1000000005;
            for(int i = 0; i + K - 1 < N; i++)
            {
                int sub = Height[i] - Height[i+K-1];
                if(sub < min) min = sub;
            }
            cout << min << endl;
        }
    }
 
    return 0;
}