Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 a + b + c =d가 되도록 배열에서 가장 큰 d 찾기


정수 집합이 있다고 가정합니다. d =a + b + c인 숫자 'd'를 찾아야 하고 (a + b + c)를 최대화해야 하며, a, b, c, d가 모두 집합에 존재합니다. 세트는 최소 하나의 요소와 최대 1000개의 요소를 보유합니다. 각 요소는 유한한 수입니다. 집합이 {2, 3, 5, 7, 12}이면 12가 가장 큽니다. d. 이것은 2 + 3 + 7로 나타낼 수 있습니다.

이 문제를 해결하기 위해 해싱 기술을 사용할 수 있습니다. (a + b)의 모든 쌍의 합계를 해시 테이블에 저장한 다음 모든 쌍 (c, d)을 통과하고 검색(d - c)이 테이블에 있는지 여부를 확인합니다. 일치하는 항목이 하나라도 발견되면 동일한 요소가 두 개 없고 동일한 요소가 두 번 고려되지 않는지 확인하십시오.

#include<iostream>
#include<unordered_map>
#include<climits>
using namespace std;
int findElementsInSet(int arr[], int n) {
   unordered_map<int, pair<int, int> > table;
   for (int i = 0; i < n - 1; i++)
      for (int j = i + 1; j < n; j++)
         table[arr[i] + arr[j]] = { i, j };
      int d = INT_MIN;
      for (int i = 0; i < n - 1; i++) {
         for (int j = i + 1; j < n; j++) {
            int abs_diff = abs(arr[i] - arr[j]);
            if (table.find(abs_diff) != table.end()) {
               pair<int, int> p = table[abs_diff];
               if (p.first != i && p.first != j && p.second != i && p.second != j) d = max(d, max(arr[i], arr[j]));
            }
         }
      }
   return d;
}
int main() {
   int arr[] = { 2, 3, 5, 7, 12 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int res = findElementsInSet(arr, n);
   if (res == INT_MIN)
      cout << "Cannot find the value of d";
   else
      cout << "Max value of d is " << res;
}

출력

Max value of d is 12