SPOJ.COM - Thuật toán bài FASHION - Fashion Shows

Đề bài:

Một cuộc thi biểu diễn thời trang đánh giá những người tham gia dựa vào độ hot của họ. Có hai chương trình khác nhau được tổ chức, một cho đàn ông và một cho đàn bà. Thời gian của chương trình thứ 3 vẫn chưa được quyết định.

Bây giờ kết quả của hai chương trình trước đã được công bố. Những người tham gia của hai chương trình đã hẹn nhau, tuy nhiên họ khó khăn trong việc tìm ra đối tác của mình. Maximum Match dating serive (MMDS) đã giúp họ bằng cách kết nối họ sao cho tối đa hóa được độ hot của họ.

Nếu một người đàn ông được đánh giá độ hot là x, và người phụ nữ là y thì giá trị của họ sẽ là x*y. Cả hai chương trình, mỗi cái bao gồm N ứng viên. MMDS đã làm xong công việc của họ. Công việc của bạn là tìm ra tổng độ hot của họ.

Đầu vào

Dòng đầu tiên là số lượng test case t. Sau đó là các test case. Mỗi cái bao gồm 3 dòng. Dòng đầu tiên là số nguyên N, 1 <= N <= 1000. Dòng thứ 2 chứa N số nguyên biểu diễn mức điểm của những người đàn ông. Dòng thứ 3 gồm N số nguyên biểu diễn mức điểm của những người phụ nữ. Tất cả độ hot có giá trị từ 0 đến 10.

Đầu ra

Với mỗi test case, in ra một số nguyên là tổng độ hot của họ theo cách của MMDS đã làm.

Ví dụ

Đầu vào:

2
2
1 1
3 2
3
2 3 2
1 3 2

Đầu ra:

5
15

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

Phân tích

• Bài toán này mình nhận ra rằng, để kết quả lớn nhất thì ta phải nhân các giá trị lớn nhất với nhau. Từ đó suy ra mình sẽ phải sắp xếp lại dãy điểm của đàn ông và phụ nữ.

• Có nhiều cách sắp xếp tuy nhiên cách nhanh và đơn giản nhất là sử dụng Counting Sort (sử dụng mảng đếm tần suất). Bởi lẽ độ hot chỉ có giá trị từ 0 đến 10.

• Sau đây mời bạn theo dõi cách mình triển khai thuật toán tham lam Greedy của mình để giải bài toán này.

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;

int main()
{
	//freopen("input.txt","r",stdin);
	int Testcase = 0;
	cin >> Testcase;
	for(int tc = 0; tc < Testcase; tc++)
	{
		int n = 0;
		cin >> n;

		// Mảng đếm số lượng người có lượng hot i của của nam và nữ
		int cnt_men[11], cnt_wen[11];
		for(int i = 0; i < 11; i++)
		{
			cnt_men[i] = 0;
			cnt_wen[i] = 0;
		}

		// Nhập đầu vào và đếm số người ứng với độ hot đã cho
		// nam
		for(int i = 0; i < n; i++)
		{
			int temp = 0;
			cin >> temp;
			cnt_men[temp]++;
		}
		// nữ
		for(int i = 0; i < n; i++)
		{
			int temp = 0;
			cin >> temp;
			cnt_wen[temp]++;
		}

		// Sắp xếp độ hot cho n người nam dùng counting sort
		int *men = new int[n];
		int id_men = 0;
		for(int i = 0; i <= 10; i++)
			for(int j = 0; j < cnt_men[i]; j++)
				men[id_men++] = i;

		// Sắp xếp độ hot cho n người nữ dùng counting sort
		int *wen = new int[n];
		int id_wen = 0;
		for(int i = 0; i <= 10; i++)
			for(int j = 0; j < cnt_wen[i]; j++)
				wen[id_wen++] = i;

		// Tính độ hot tổng
		int sum = 0;
		for(int i = 0; i < n; i++)
			sum += men[i] * wen[i];

		cout << sum << endl;
		delete[] wen;
		delete[] men;
	}
	return 0;
}