SPOJ.COM - Thuật toán bài KOIREP - Representatives

Đề bài:

Có N lớp ở trường và mỗi lớp có M học sinh. Sắp tới có một cuộc thi chạy 100 m và người đại diện cho mỗi lớp sẽ được chọn để tham gia cuộc thi. Bạn được giao cho một nhiệm vụ là chọn ra những người đại diện này. Bởi vì, bạn không muốn cuộc đua trở nên 1 chiều, nên bạn muốn chọn người đại diện của các lớp sao cho chênh lệnh khả năng giữa người tốt nhất và người kém nhất là ít nhất.

Ví dụ: Nếu N = 3 và M = 4. Mỗi lớp có những học sinh với khả năng như sau:

• Lớp 1: {12,16,67,43}
• Lớp 2: {7,17,68,48}
• Lớp 3: {14,15,77,54}

Trường hợp tốt nhất là chọn ra học sinh với khả năng 16 ở lớp 1, học sinh có khả năng 17 ở lớp 2 và học sinh có khả năng 15 ở lớp 3. Khi đó, độ chênh lệch là: 17 - 15 = 2.

Nhiệm vụ của bạn là hãy tìm ra độ chênh lệch nhỏ nhất có thể bởi việc chọn ra người đại diện cho mỗi lớp.

Đầu vào

Dòng đầu tiên là số N và M (1<=N<=1000, 1<=M<=1000). N dòng tiếp theo, mỗi dòng có M số - miêu tả khả năng của các học sinh. Khả năng của học sinh là một con số trong khoảng từ 0 đến 10^9.

Đầu ra

In ra độ chênh lệch nhỏ nhất cần tìm.

Ví dụ

Trường hợp 1:

Đầu vào:

3 4
12 16 67 43
7 17 68 48
14 15 77 54

Đầu ra:

2

Trường hợp 2:

Đầu vào:

4 3
10 20 30
40 50 60
70 80 90
100 110 120

Đầu ra:

70

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

Phân tích

• Mình sẽ sử dụng thuật toán tham lam Greedy để giải bài toán.

• Ở đây, trước tiên mình dùng sắp xếp trộn để sắp xếp tất cả người của các lớp theo thứ tăng dần về khả năng.

• Tiếp đến mình sẽ dùng phương pháp cửa sổ để duyệt dãy đã sắp xếp. Cửa sổ ở đây có độ dài là n để tìm ra dãy n người thỏa mãn thuộc n lớp khác nhau. Khi đó, mình chỉ cần tìm ra trong các trường hợp đó trường hợp có độ chênh lệnh nhỏ nhất. Đó chính là kết quả của bài toán.

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<stdio.h>

typedef struct{
	int group;
	int ability;
}Person;

Person person[1000005];
int leng;
int cnt[1000];

// Sắp xếp trộn
void Merge(Person *p, int left, int m, int right)
{
	int l = left, r = m + 1, k = 0;
	Person *temp = new Person[right - left + 1];

	while(l <= m && r <= right)
	{
		if(p[l].ability < p[r].ability) temp[k++] = p[l++];
		else temp[k++] = p[r++];
	}

	while(l <= m) temp[k++] = p[l++];
	while(r <= right) temp[k++] = p[r++];

	for(int i = 0; i < k; i++)
		p[i+left] = temp[i];
	delete[] temp;
}

void MergeSort(Person *p, int left, int right)
{
	int m;
	if(left < right)
	{
		m = (left + right)/2;
		MergeSort(p,left,m);
		MergeSort(p,m+1,right);
		Merge(p,left,m,right);
	}
}

int main()
{
	int n,m,t;
	scanf("%d%d",&n,&m);
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
		{
			scanf("%d",&t);
			person[leng].group = i;
			person[leng].ability = t;
			leng++;
		}

	MergeSort(person, 0, leng-1);

	for(int i = 0; i < n; i++)
		cnt[i] = 0;

	int num_group = 0;
	int l = 0, r = 0;
	int _min = 1000000005;

	while(r < n*m)
	{
		int pos = person[r].group;
		if(num_group < n)
		{
			if(cnt[pos] == 0) num_group++;
			cnt[pos]++;
			r++;
		}
		else
		{
			while(num_group >= n)
			{
				int t = person[l].group;
				cnt[t]--;
				if(cnt[t] == 0) num_group--;
				l++;
			}
			int temp = person[r-1].ability - person[l-1].ability;
			if(temp < _min) _min = temp;
		}
	}
	printf("%d\n",_min);
	return 0;
}