|ai + aj – k|의 최소 가능한 값 C++에서 주어진 배열과 k에 대해

문제 설명

n개의 정수와 정수 K의 배열이 주어졌습니다. |ai + aj – k| 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