最大サイズ2の最小パーティションと、C++で指定された値によって制限される合計

問題の説明

正の数の配列arr[]が与えられた場合、次のプロパティを満たす配列内のセットの最小数を見つけます。

• セットには、最大2つの要素を含めることができます。 2つの要素は連続している必要はありません。
• セットの要素の合計は、指定されたキー以下である必要があります。与えられたキーが最大の配列要素以上であると想定される場合があります。

例

arr [] ={1、2、3、4}およびk =5の場合、次の2つのペアを作成できます-

{1、4}および{2、3}

アルゴリズム

• 配列を並べ替える
• ソートされた配列の2つのコーナーから2つのポインターを開始します。それらの合計が指定されたキー以下の場合は、それらのセットを作成します。それ以外の場合は、最後の要素のみを考慮します

例

#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