SPOJ.COM - Thuật toán bài AMR10G - Christmas Play

Đề bài:

Lớp mẫu giáo của con mình đang chuẩn bị một vở kịch cho Noel (hy vọng rằng con trai mình sẽ giữ vai trò đội trưởng). Những đứa trẻ rất là hào hứng, tuy nhiên giáo viên của chúng thì lại rất vất vả. Cô ấy phải chuẩn bị phục trang cho K người lính. Cô ấy muốn mua tất cả trang phục với cùng 1 kích cỡ. Độ dài của chúng có thể thay đổi một lượng nhỏ sau này bởi cha mẹ của những đứa trẻ.

Vì vậy, cô ấy đã lấy chiều cao của tất cả những đứa trẻ. Bạn hãy giúp cô ấy chọn ra K đứa trẻ trong N đứa để đóng vai binh lính, sao cho chiều cao giữa đứa cao nhất và đứa thấp nhất là nhỏ nhất, nhờ đó mà sự thay đổi là ít nhất. Và nói với cô ấy sự chênh lệnh nhỏ nhất đó.

Đầu vào:

Dòng đầu tiên bao gồm số lượng test case T. Mỗi test case bao gồm 2 dòng. Dòng đầu tiên của mỗi test case bao gồm 2 số nguyên N và K. Dòng thứ hai bao gồm N số nguyên là chiều cao của N đứa trẻ.

Đầu ra:

Với mỗi test case, in ra kết quả tương ứng.

Ràng buộc:

T <= 30 
1 <= K <= N <= 20000 
1 <= chiều cao <= 1000000000

Ví dụ

Đầu vào:

3 
3 1 
2 5 4 
3 2 
5 2 4 
3 3 
2 5 4

Đầu ra:

0 
1 
3 

Giải thích:

• Test case số 1: giáo viên chỉ cần chọn 1 người làm binh lính, vì vậy, cô ấy có thể chọn bất kì ai làm binh lính. Do đó, độ chênh lệnh chiều cao cần tìm là 0

• Test case số 2: giáo viên có thể chọn hai đứa trẻ có chiều cao là 4 và 5. Khi đó kết quả là 1

• Test case số 3: giáo viên bắt buộc phải chọn hết, nên đáp án là 5 - 2 = 3

Bạn có thể tham khảo đề bài tiếng anh và submit tại đây: http://www.spoj.com/problems/AMR10G/

Phân tích:

• Đầu tiên, nếu phải chọn 1 đứa trẻ thì kết quả là 0

• Nếu phải trọn K > 1 đứa trẻ, ta sẽ sắp xếp dãy chiều cao của chúng theo thứ tự tăng dần, hoặc giảm dần Sau đó, ta chỉ cần kiểm tra độ chênh lệnh chiều cao giữa đứa trẻ thứ i và i + K - 1. Tìm ra trường hợp nào có độ chênh lệnh nhỏ nhất là kết quả cần tìm

Lời giải

Bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của mình nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code mình viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của bạn.

Code C/C++:

#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;
}