数组中最大尺寸为 2，并且其总和小于给定值的最小划分

问题陈述

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

  • 一个集合最多包含两个元素。这两个元素无需连续。
  • 集合中元素之和应小于或等于给定的键值。可以假设给定的键值大于或等于数组中的最大元素。

示例

如果 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

更新于：2019 年 11 月 22 日

69 次浏览

开启您的 职业生涯

完成课程获得认证

开始
广告