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