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

#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;
}