Phân vùng tối thiểu có kích thước tối đa 2 và tổng được giới hạn bởi giá trị nhất định trong C ++

Tuyên bố vấn đề

Cho một mảng arr [] các số dương, hãy tìm số bộ nhỏ nhất trong mảng thỏa mãn thuộc tính sau,

• Một tập hợp có thể chứa tối đa hai phần tử trong đó. Hai yếu tố không cần phải tiếp giáp với nhau.
• Tổng các phần tử của tập hợp phải nhỏ hơn hoặc bằng Khoá đã cho. Có thể giả định rằng khóa đã cho lớn hơn hoặc bằng phần tử mảng lớn nhất.

Ví dụ

Nếu arr [] ={1, 2, 3, 4} và k =5 thì có thể tạo 2 cặp sau -

{1, 4} và {2, 3}

Thuật toán

• Sắp xếp mảng
• Bắt đầu hai con trỏ từ hai góc của mảng đã sắp xếp. Nếu tổng của chúng nhỏ hơn hoặc bằng khóa đã cho, thì chúng tôi tạo tập hợp các khóa đó, nếu không, chúng tôi chỉ xem xét phần tử cuối cùng

Ví dụ

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

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Minimum set = 2