SPOJ.COM - Thuật toán bài NDCCARD - Các lá bài Blackjack

Posted on October 20th, 2016

Đề bài:

Blackjack là trò chơi đánh bài khá phổ biến, mục tiêu là có được những lá bài mà tổng của nó là lớn nhất nhưng không vượt quá 21. Lấy ý tưởng từ trò chơi này bạn khaihanhdk huytion156 thanhdat01234 đã sáng tạo ra một phiên bản mới của trò chơi cho riêng mình.

Trong phiên bản trò chơi mới này bạn đã viết lên mỗi lá bài một số nguyên dương. Người tham gia trò chơi được cung cấp một tập gồm N lá bài và một số nguyên dương M. Nhiệm vụ của người chơi là phải chọn ra 3 lá bài từ tập lá bài đã cho sao cho tổng các số trên 3 lá bài đã chọn là lớn nhất và không vượt quá M.

Yêu cầu:  Bạn hãy tìm kết quả tốt nhất có thể có của trò chơi trên.

Đầu vào

Dòng đầu ghi số nguyên dương N, M (N <= 10000 , M <= 500000). Dòng sau ghi N số nguyên dương đôi một khác nhau là các số được ghi trên N lá bài ( 1 ≤ a[i] ≤ 10000).

Đầu ra

Ghi trên một dòng duy nhất là kết quả bài toán. Test luôn đảm bảo có kết quả.

Ví dụ

Đầu vào:

6 20 
7 9 6 2 1 5

Đầu ra:

20 

Giải thích:

Chọn các lá bài mang số 9 , 6 , 5 ta có 9+6+5 = 20 <= M

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

Phân tích

Yêu cầu tìm ra 3 số có tổng không vượt quá M. Do đó, trong quá trình nhập đầu vào, mình sẽ loại bỏ luôn những số > M.

Ở đây, mình sẽ dùng thuật toán sắp xếp trộn Merge Sort để sắp xếp dãy đầu vào theo thứ tự tăng dần.

Sau đó, mình sẽ duyệt dãy sau khi sắp xếp. Với mỗi cặp 2 số a[i1][j1]a[i2][j2], mình sẽ sử dụng thuật toán chia để trị - Divide and Conquer để tìm ra số lớn nhất thỏa mãn tổng 3 số không vượt quá M. Sau khi duyệt hết tất cả các trường hợp, mình sẽ tìm được kết quả.

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

int N, M;			
int a[MAX];
int MaxSum;     // Giá trị tổng lớn nhất không lớn hơn M.
int Leng;       // Số các số < M - 1

// Sắp xếp dùng Merge Sort
void Merge(int *arr, int left, int m, int right)
{
	int *tmp = new int[right - left + 1];
	int l = left, r = m + 1, k = 0;

	while(l <= m && r <= right)
	{
		if(a[l] < a[r]) tmp[k++] = a[l++];
		else tmp[k++] = a[r++];
	}

	while(l <= m) tmp[k++] = a[l++];

	while(r <= right) tmp[k++] = a[r++];

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

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

/*
* Tìm kiếm nhị phân
* Tìm ra số lớn nhất mà không lớn hơn giá trị value
*/
int BinarySearch(int value)
{
	int left = 0, right = Leng - 1;
	int x = 0;

	while(left < right - 1)
	{
		x = (left + right) / 2;
		if(a[x] <= value) left = x;
		else if(a[x] > value) right = x - 1; 
	}

	if(a[right] <= value) return right;

	return left;
}

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

	// Nhập đầu vào, đồng thời loại bỏ những số lớn hơn hoặc bằng M - 1
	// Vì các số trong dãy >= 1
	MaxSum = Leng = 0;
	cin >> N >> M;
	for(int i = 0; i < N; i++)
	{
		int t = 0;
		cin >> t;
		if(t < M - 1) a[Leng++] = t;
	}
	
	// Sắp xếp dãy tăng dần
	MergeSort(a, 0, Leng-1);

	// Kiểm tra để dừng sớm
	bool Finish = false;

	// Duyệt mảng
	for(int i = 0; i < Leng; i++)
	{
		for(int j = i + 1; j < Leng; j++)
		{
			int temp = M - (a[i] + a[j]);
			if(temp <= 0){
				Finish = true;
				break;
			}

			// Dùng tìm kiếm nhị phân tìm ra số lớn nhất và không lớn hơn số 'temp'
			// Số tìm được phải khác hai số tại: i và j
			int k = BinarySearch(temp);
			if(k == i || k == j) break;

			int sum = a[k]+ a[i] + a[j];
			if(sum > MaxSum) MaxSum = sum;
		}
		if(Finish) break;
	}

	// In kết quả
	cout << MaxSum << endl;

	return 0;
}

★ Nếu bạn thấy bài viết này hay thì hãy theo dõi mình trên Facebook để nhận được thông báo khi có bài viết mới nhất nhé:

Xin chào và hẹn gặp lại, thân ái!