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

25/09/2016 6 minutes read

Đề 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:

5 3

Đầu ra:

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

Các 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:

(Các 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 tôi 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 tôi 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 các 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;
      
        }

view raw AGGRCOW.cpp hosted with ❤ by GitHub

Code by Phạm Văn Lâm

spoj, Chia để trị - Divide and Conquer

phạm văn lâm, spoj.com, thuật toán, thuật toán spoj.com, chia để trị divide and conquer

Quay lại

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