Created
September 15, 2018 05:55
-
-
Save completejavascript/8d0373a3fec75bdcd8386d9f7a17e0bb to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment