SPOJ.COM - Thuật toán bài PQUEUE - Printer Queue

Đề bài:

Chỉ có một cái máy in duy nhất và nó đang phải làm việc rất nhiều. Thỉnh thoảng có hàng trăm công việc ở hàng đợi của máy in. Và bạn phải đợi hàng giờ đồng hồ chỉ để in một trang giấy.

Bởi vì một số công việc là quan trọng hơn những cái khác, nên Hacker General đã phát minh ra một hệ thống hàng đợi ưu tiên cho máy in. Bây giờ, mỗi công việc sẽ được gán một giá trị độ ưu tiên từ 1 đến 9. Trong đó, 9 là độ ưu tiên cao nhất và 1 là độ ưu tiên thấp nhất. Máy in làm việc theo nguyên lý sau:

• Công việc j đầu tiên được lấy từ hàng đợi
• Nếu có công việc nào mà độ ưu tiên cao hơn công việc j thì cho j xuống cuối của hàng đợi và không in nó.
• Ngược lại, in công việc j (không cho nó xuống cuối cùng của hàng đợi)

Theo cách này, công việc in trở nên rất nhanh. Dĩ nhiên, sẽ có những cái phải chờ đợi để được in. Nhưng đó chính là cuộc sống.

Vấn đề của bạn với chính sách mới này là rất khó để xác định xem khi nào thì công việc của bạn được in. Bạn quyết định viết một chương trình để xác định nó. Chương trình này được đưa cho trạng thái hiện tại của hàng đợi (danh sách của thứ tự ưu tiên), cũng như là vị trí công việc của bạn. Bạn phải tính được khi nào thì công việc của bạn được hoàn thành. Giả sử rằng sẽ không có công việc nào nữa được cho vào máy in. Để cho đơn giản, giả sử việc in một công việc mất 1 phút để hoàn thành. Việc cho vào hay lấy ra từ hàng đợi xảy ra tức thời.

Đầu vào

Dòng đầu tiên là số nguyên t, t <= 100, là số lượng test case. Mỗi test case sẽ bao gồm 2 số nguyên n và m. Trong đó, n là số lượng công việc và m là vị trí công việc của bạn (1 ≤ n ≤ 100, 0 ≤ m ≤ n-1). Vị trí công việc đầu tiên là 0, công việc thứ 2 là 1,... Dòng tiếp theo là n số nguyên, thuộc từ 1 đến 9, cho biết độ ưu tiên của các công việc. Số đầu tiên là độ ưu tiên của công việc thứ nhất, số tiếp theo là độ ưu tiên của công việc thứ 2,...

Đầu ra

Với mỗi một test case, in ra trên 1 dòng, chứa 1 số là số phút cần phải đợi cho đến khi công việc của bạn được hoàn thành. Giả sử không có công việc nào được thêm vào máy in.

Ví dụ

Đầu vào:

3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

Đầu ra:

1
2
5

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

Phân tích

• Bài toán này hoàn toàn là việc sử dụng hàng đợi. Nên có thể xếp vào loạt bài sử dụng thuật toán tham lam Greedy.

• Một chú ý ở đây là: để đánh dấu vị trí công việc cần tìm thì mình sẽ chuyển giá trị của nó về âm. Nghĩa là nếu công việc cần tính có độ ưu tiên là 6, thì mình sẽ chuyển nó về -6. Như vậy, nếu muốn so sánh độ ưu tiên thì mình chỉ cần so sánh giá trị tuyệt đối của chúng.

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 = 105;

int N, M;
int front, rear, leng, queue[MAX];
int numMinute;

int Abs(int a)
{
	if(a >= 0) return a;
	return -a;
}

void Enqueue(int p)
{
	queue[rear] = p;
	rear = (rear + 1) % MAX;
	leng++;
}

int Dequeue()
{
	int p = queue[front];
	front = (front + 1) % MAX;
	leng--;
	return p;
}

int main()
{
	freopen("input.txt","r",stdin);
	int T;
	cin >> T;
	for(int tc = 0; tc < T; tc++)
	{
		// Nhập đầu vào
		cin >> N >> M;
		for(int i = 0; i < N; i++)
			cin >> queue[i];

		// Đánh dấu vị trí công việc cần hoàn thành
		// bằng cách chuyển về giá trị âm
		queue[M] = -queue[M];

		front = 0;
		rear  = N;
		leng  = N;
		numMinute = 0;

		while(leng > 0)
		{
			int k = Dequeue();
			bool IsPrint = true;

			// Duyệt hàng đợi từ front đến rear
			for(int i = front; i != rear; i = (i+1) % MAX)
			{
				// Nếu tồn tại công việc có độ ưu tiên lớn hơn k
				// thì cho k xuống cuối hàng đợi
				if(Abs(k) < Abs(queue[i]))
				{
					IsPrint = false;
					Enqueue(k);
					break;
				}
			}

			// Ngược lại, nếu không tìm thấy, thì chứng tỏ k có độ ưu tiên cao nhất.
			if(IsPrint)
			{
				numMinute++;
				// Nếu k < 0 thì đó là công việc cần tìm
				if(k < 0)
				{
					cout << numMinute << endl;
					break;
				}
			}
		}
	}
	return 0;
}