SPOJ.COM - Thuật toán bài AGGRCOW - Aggressive cows

Posted on September 25th, 2016

Đề bài:

Trung đã xây dựng một cái chuồng mới rất dài, với N (2 <= N <= 100000) ngăn. Các ngăn được xếp theo một đường thẳng tại vị trí x1, x2,…, xN (0 <= xi <= 1000000000). Trung nuôi C con bò (2 <= C <= N). Và chúng không thích cách bố trí của cái chuồng này. Do đó, chúng luôn gây sự với những con bò mới khi nó được đặt vào một ngăn nào đó. Để ngăn cho những con bò này đánh nhau, Trung muốn đưa các con bò vào chuồng sao cho, khoảng cách ngắn nhất giữa hai con bất kì là lớn nhất có thể. Hỏi khoảng cách này là bao nhiêu?

Đầu vào

t - số lượng test cases, sau đó là t test cases theo sau.

Dòng 1: Bao gồm 2 số nguyên ngăn cách bởi dấu cách: N và C

Dòng 2…N+1: Dòng i + 1 chứa số nguyên xi là vị trí của chuồng thứ i.

Đầu ra

Với mỗi test case, in ra một số nguyên - là khoảng cách cần tìm.

Ví dụ

Đầu vào:

1 
5 3 
1 
2 
8 
4 
9 

Đầu ra:

3 

Giải thích: Trung có thể đặt 3 con bò vào các vị trí 1, 4 và 8. Do đó kết quả là 3

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

Phân tích

Với bài toán này, ta sẽ sắp xếp lại mảng vị trí các ngăn sao cho toạ độ tăng dần. Sau đó dùng thuật toán chia để trị - Divide and Conquer, để tìm ra kết quả.

Chú ý: khoảng cách ngắn nhất giữa hai ngăn tối thiểu là 1, và tối đa là khoảng cách giữa ngăn đầu và ngăn cuối.

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 = 100005;
 
int Answer;             // Lưu kết quả
int N;                  // Lưu số lượng ngăn trong chuồng
int C;                  // Lưu số lượng con bò
int X[MAX];             // Lưu toạ độ các ngăn
int Left, Right;
 
void Merge(int *a, int left, int m, int right)
{
    int *temp = new int[right-left+1];
    int k = 0, i = left, j = m + 1;
 
    while(i <= m && j <= right)
    {
        if(a[i] < a[j]) temp[k++] = a[i++];
        else temp[k++] = a[j++];
    }
 
    while(i <= m) temp[k++] = a[i++];
 
    while(j <= right) temp[k++] = a[j++];
 
    for(int i = 0; i < k; i++)
        a[i + left] = temp[i];
 
    delete[] temp;
}
 
void MergeSort(int *a, int left, int right)
{
    int m;
    if(left < right)
    {
        m = (left + right) / 2;
        MergeSort(a, left, m);
        MergeSort(a, m + 1, left);
        Merge(a, left, m, right);
    }
}
 
bool IsValid()
{
    // Ta sẽ xếp thử các con bò vào các ngăn, bắt đầu từ ngăn đầu tiên
    int pos = 0, cnt = 1, delta = 0, i = 1;
 
    while(i < N)
    {
        // Khoảng cách giữa ngăn thứ 'i' và ngăn 'pos'
        delta = X[i] - X[pos];
 
        // Vì Answer ở đây là khoảng cách ngắn nhất giữa các chuồng
        // Nên buộc delta phải lớn hơn Answer thì ta mới xếp được
        if(delta >= Answer)
        {
            pos = i;
            cnt++;
        }
        
        i++;
 
        // Nếu xếp được hết C con bò thì thoả mãn,
        // ngược lại là không thể xếp C con bò vào N ngăn mà khoảng cách ngắn nhất 
        // giữa hai chuồng là Answer
        if(cnt == C) return true;
    }
    
    return false;
}
 
int main()
{
    ios::sync_with_stdio(false);
    
    // Comment dòng này trước khi submit
    freopen("input.txt","r",stdin);
 
    int T;
    cin >> T;
 
    for(int tc = 0; tc < T; tc++)
    {
        // Input
        Answer = 0;
 
        cin >> N >> C;
        for(int i = 0; i < N; i++)
            cin >> X[i];
 
        // Implementing code below
        MergeSort(X, 0, N-1);
 
        // Binary search
        Left  = 1;
        Right = X[N-1] - X[0];
 
        while (Left < Right - 1)
        {
            // Answer chính là khoảng cách ngắn nhất đang xét
            // giữa các ngăn
            Answer = (Left + Right) / 2;
 
            if (IsValid()) Left = Answer;
            else Right = Answer - 1;
        }
 
        // Kiểm tra xem là tại Left hoặc Right thoả mãn thì lấy
        Answer = Right;
        if(!IsValid()) Answer = Left;
 
        // ouput
        cout << Answer << endl;
    }
 
    return 0;
}

★ Nếu bạn thấy bài viết này hay thì hãy theo dõi mình trên Facebook để nhận được thông báo khi có bài viết mới nhất nhé:

Xin chào và hẹn gặp lại, thân ái!