| ai + aj –k|の可能な最小値C++で指定された配列とkに対して

問題の説明

n個の整数と整数Kの配列が与えられます。|ai+ aj – k|の絶対値となるような順序付けされていないペアの総数{i、j}を見つけます。 i！=jの場合は最小限に抑えられます。

例

arr [] ={0、4、6、2、4}およびk =7の場合、最小値を1として次の5つのペアを作成できます

{0、6}、{4、2}、{4、4}、{6、2}、{2、4}

アルゴリズム

可能なすべてのペアを反復処理し、各ペアについて、（ai + aj – K）の値が現在の最小値であるnotよりも小さいかどうかを確認します。したがって、上記の条件の結果として、合計3つのケースがあります-

• abs（ai + aj – K）>最小-このペアは可能な最小値にカウントされないため、何もしません。
• abs（ai + aj – K）=最小-ペアのカウントをインクリメントして、可能な最小値にします。
• abs（ai + aj – K）<最小-最小値を更新し、カウントを1に設定します。

例

#include <iostream>
#include <climits>
#include <cmath>
using namespace std;
void getPairs(int *arr, int n, int k) {
   int minValue = INT_MAX;
   int pairs = 0;
   for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
         int val = abs(arr[i] + arr[j] - k); if (val < minValue) {
            minValue = val;
            pairs = 1;
         } else if (val == minValue) {
            ++pairs;
         }
      }
   }
   cout << "Min value = " << minValue << endl; cout << "Total pairs = " << pairs << endl;
}
int main() {
   int arr[] = {0, 4, 6, 2, 4};
   int k = 7;
   int n = sizeof(arr) / sizeof(arr[0]);
   getPairs(arr, n, k);
   return 0;
}

出力

上記のプログラムをコンパイルして実行する場合。次の出力を生成します-

Min value= 1
Total pairs = 5