SPOJ.COM - Thuật toán bài IITKWPCO - Create Collections

Đề bài:

Little Feluda rất thích chơi. Như bạn biết, anh ấy chỉ thích chơi với những con số. Vì vậy anh ấy được đưa cho những số n. Bây giờ hãy nhóm những số đó thành nhóm gồm 2 số. Anh ấy có thể định dạng nhóm gồm 2 số nếu số nhỏ hơn bằng một nửa số lớn hơn.

Cho trước những số n. Hãy tìm ra số lượng nhóm tối đa thỏa mãn điều kiện trên.

Đầu vào

T: số lượng test case (1 <= T <= 100)

Mỗi test case:

Dòng đầu tiên chứa số n: (1 <= n <= 100)

Dòng tiếp theo chứa n số cách nhau bởi một dấu cách. Mỗi số sẽ thuộc từ 1 đến 10^6.

Đầu ra

Với mỗi test case, in ra trên một dòng kết quả tìm được.

Ví dụ

Đầu vào:

2
2
1 2
3 
1 2 4

Đầu ra:

1
1

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

Phân tích

• Mình sẽ sử dụng thuật toán tham lam Greedy để giải. Thuật toán của mình là mình sẽ sử dụng mảng đếm để đếm tần suất xuất hiện của các số.

• Sau đó, mình sẽ duyệt từ 0 đến số MAX (1000000). Mình sẽ kiểm tra nếu giá trị đếm tại i và 2*i là lớn hơn 0. Thì lúc này sẽ xuất hiện cặp đôi có dạng như đầu bài. Chỉ cần tìm ra giá trị đếm nào nhỏ hơn thì đó là số cặp đôi thỏa mãn tìm thấy. Sau đó, cập nhật lại mảng đếm và tiếp tục duyệt cho đến hết.

• Xin mời bạn theo dõi cách triển khai của mình sau đâ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<stdio.h>
const int MAX = 1000005;
int cnt[MAX];

int main()
{
	int T;
	scanf("%d",&T);
	for(int tc = 0; tc < T; tc++)
	{
		int n;
		scanf("%d",&n);

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

		for(int i = 0; i < n; i++)
		{
			int t;
			scanf("%d",&t);
			cnt[t]++;
		}

		int max_collection = 0;
		for(int i = 0; i < MAX; i++)
		{
			if((cnt[i]==0) || (2*i >= MAX) || (cnt[2*i]==0)) continue;
			if(cnt[i] < cnt[2*i])
			{
				max_collection += cnt[i];
				cnt[2*i] -= cnt[i];
			}
			else
			{
				max_collection += cnt[2*i];
				cnt[2*i]= 0;
			}
		}
		printf("%d\n",max_collection);
	}
	return 0;
}