| ai + aj – k |的最小可能值 给定数组和C ++中的k

  • Z时代
  • 2024-01-10
  • 分类：综合

问题陈述

给您一个由n个整数和一个整数K组成的数组。找到总数为{i，j}的无序对的数量，使得| ai + aj – k |的绝对值 当i！= j时，可能性最小。

示例

如果arr [] = {0，4，6，2，4}并且k = 7，那么我们可以创建以下5对，其最小值为1

{0，6}，{4，2}，{4，4}，{6，2}，{2，4}

算法

遍历所有可能的对，对于每对，我们将检查（ai + aj – K）的值是否小于我们当前的最小值not。因此，根据上述条件，我们总共有三种情况-

  • 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

以上是 | ai + aj – k |的最小可能值 给定数组和C ++中的k 的全部内容， 来源链接： utcz.com/z/317079.html

回到顶部