C ++中最大大小为2的最小分区和总和受给定值限制

问题陈述

给定一个数组arr []为正数，找到满足以下属性的数组中的最小集合数，

• 一个集合中最多可以包含两个元素。这两个元素不必是连续的。

• set元素的总和应小于或等于给定的Key。可以假定给定键大于或等于最大数组元素。

示例

如果arr [] = {1,2,3,4}并且k = 5，那么可以创建以下两对-

{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