SPOJ.COM - Thuật toán bài QUE1 - Queue (Rookie)

Đề bài:

Có N ngưới đang đứng ở một hàng đợi. Bạn được đưa cho chiều cao của mỗi người và số những người cao hơn và đứng trước anh ta. Bạn hãy tìm ra vị trí của mỗi người.

Đầu vào

Bắt đầu bằng số nguyên T - là số lượng test case. Sau đó là T test case. Mỗi test case bao gồm 3 dòng. Dòng đầu tiên là số nguyên N. Dòng thứ hai là N số nguyên biểu diễn chiều cao của N người. Dòng thứ ba là N số nguyên biểu diễn số người cao hơn đứng trước anh ta.

Đầu ra

In ra một dòng cho mỗi test case, bao gồm chiều cao của N người theo đúng thứ tự của vị trí đứng.

Ràng buộc:

0 < T <= 100 
0 < N <= 1000 

Ví dụ

Đầu vào:

1
5
33 11 22 44 55
0 2 1 1 0

Đầu ra:

33 22 11 55 44

Bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/QUE1/

Phân tích

Ở đây mình sử dụng thuật toán tham lam Greedy để giải quyết bài toán.

Trước tiên, mình sẽ sắp xếp dãy theo thứ tự tăng dần của độ cao. Sau khi có có dãy theo đúng thứ tự rồi, việc còn lại là tìm vị trí đúng cho từng người là vô cùng đơn giản.

Mình sử dụng một mảng để lưu kết quả. Với mỗi người mình sẽ duyệt từ trái sang phải và để lại số ô '-1' (tức là chưa được xếp) bằng với số người cao hơn phía trước người đang xét.

Ví dụ với bài toán trên:

• Đầu tiên sắp xếp dãy tăng dần theo chiều cao mình được 2 dãy như sau:

11 22 33 44 55
2  1  0  1  0

• Một mảng kết quả, khởi tạo các giá trị là -1:

-1 -1 -1 -1 -1

• Đầu tiên, xét chiều cao 11: do có 2 người cao hơn nên mảng kết quả trở thành:

-1 -1 11 -1 -1 (2 số -1 phía trước là 2 người có chiều cao lớn hơn và đứng trước)

• Tiếp theo, xét chiều cao 22: có 1 người cao hơn nên mảng kết quả trở thành:

-1 22 11 -1 -1

• Tương tự như vậy ta có kết quả là:

33 22 11 -1 -1
33 22 11 -1 44
33 22 11 55 44

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;

/*
* Hoán vị 2 số a và b
*/
void swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

/*
* Sắp xếp dãy theo chiều tăng dần của dãy a
* Dãy b được đi kèm theo dãy a
* left, right: chỉ số trái, phải của dãy
*/
void QuickSort_Ascending(int *a, int *b, int left, int right)
{
	int i = left, j = right;
	int pivot = a[(i+j)/2];
	while(i <= j)
	{
		while(a[i] < pivot) i++;
		while(a[j] > pivot) j--;
		if(i <= j)
		{
			swap(a[i],a[j]);
			swap(b[i],b[j]);
			i++;
			j--;
		}
	}
	if(left < j) QuickSort_Ascending(a,b,left,j);
	if(i < right) QuickSort_Ascending(a,b,i,right);
}

int main()
{
	ios::sync_with_stdio(false);
	freopen("input.txt","r",stdin);

	int T, N;
	int height[1000];		// Lưu chiều cao của N người
	int numTallerBef[1000]; // Lưu số người cao hơn đứng trước
	int result[1000];		// Lưu dãy kết quả

	cin >> T;
	for(int i = 0; i < T; i++)
	{
		// Nhập đầu vào
		cin >> N;
		for(int i = 0; i <  N; i++)
			cin >> height[i];
		for(int i = 0; i < N; i++)
		{
			cin >> numTallerBef[i];
			result[i] = -1;
		}

		// Sắp xếp lại dãy theo chiều tăng dần của chiều cao
		QuickSort_Ascending(height, numTallerBef, 0, N-1);

		// Duyệt dãy sau khi sắp xếp để tìm vị trí đúng
		int count, j, temp;
		for(int i = 0; i < N; i++)
		{
			temp = numTallerBef[i];
			j = count = 0;

			if(temp == 0)
			{
				for(j = 0; j < N; j++)
					if(result[j] == -1) break;
				result[j] = height[i];
			}
			else
			{
				for(j = 0; j < N; j++)
				{
					if(result[j] == -1) count++;
					if(count == temp && result[j+1] == -1) break;
				}
				result[j+1] = height[i];
			}
		}
		for(int i = 0; i< N; i++)
			cout << result[i] << " ";
		cout << endl;
	}
	return 0;
}