문제 설명
양수 배열 arr[]이 주어지면 배열에서 다음 속성을 만족하는 최소 집합 수를 찾습니다.
- 집합에는 최대 2개의 요소가 포함될 수 있습니다. 두 요소가 연속적일 필요는 없습니다.
- 집합 요소의 합은 주어진 키보다 작거나 같아야 합니다. 주어진 키가 가장 큰 배열 요소보다 크거나 같다고 가정할 수 있습니다.
예시
arr[] ={1, 2, 3, 4}이고 k =5이면 다음 2쌍이 생성될 수 있습니다. −
{1, 4} 및 {2, 3}
알고리즘
- 배열 정렬
- 정렬된 배열의 두 모서리에서 두 포인터를 시작합니다. 합이 주어진 키보다 작거나 같으면 집합을 만들고, 그렇지 않으면 마지막 요소만 고려합니다.
예시
#include <iostream>
#include <algorithm>
using namespace std;
int getMinSets(int *arr, int n, int key) {
int i, j;
sort (arr, arr + n);
for (i = 0, j = n - 1; i <= j; ++i) {
if (arr[i] + arr[j] <= key) {
--j;
}
}
return i;
}
int main() {
int arr[] = {1, 2, 3, 4};
int key = 5;
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum set = " << getMinSets(arr, n, key) << endl;
return 0;
} 출력
위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -
Minimum set = 2