C++에서 세 가지 다른 정렬된 배열의 최소화(max(A[i], B[j], C[k]) – min(A[i], B[j], C[k]))

컨셉

반드시 같은 크기는 아닌 주어진 3개의 정렬된 배열 A, B, C와 관련하여 가장 낮은 것, 즉 다음과 같은 트리플렛 A[i], B[j], C[k]의 최대값과 최소값 사이의 최소 절대 차이를 계산하십시오. 그것들이 각각 배열 A, B 및 C 아래에 있다는 것, 즉 최소화(max(A[i], B[j], C[k]) – min(A[i], B[j], C[k]) )).

입력 -

A : [ 2, 5, 6, 9, 11 ]
B : [ 7, 10, 16 ]
C : [ 3, 4, 7, 7 ]

출력 -

1

설명

A[i] =6 , B[j] =7, C[k] =7을 선택하면 max(A[i], B[j], C[k]) - min( A[i], B[j], C[k])) =|7-6| =1

입력 -

A = [ 6, 9, 11, 16 ]
B = [ 7, 10, 16, 79, 90 ]
C = [ 3, 4, 7, 7, 9, 9, 11 ]

출력 -

1

설명 -

A[i] =11 , b[j] =10, C[k] =11을 선택하면 max(A[i], B[j], C[k]) - min( A[i], B[j], C[k]))=|11-10| =1

방법

각 배열 A, B 및 C에서 가장 높은 요소부터 시작합니다. 따라야 할 각 단계의 시간에 답을 업데이트하려면 변수를 추적하십시오.

각 단계마다 차이를 줄이는 유일한 방법은 세 가지 요소 중 최대 요소를 줄이는 것뿐입니다.

결과적으로 이 단계의 최대 요소를 포함하는 배열에서 다음으로 높은 요소를 방문하여 응답 변수를 업데이트합니다.

최대 요소를 포함하는 배열이 종료될 때까지 이 단계를 반복해야 합니다.

예시(C++)

// 위의 접근 방식에 대한 C++ 코드

#include<bits/stdc++.h>
usingnamespacestd;
intsolve(intA1[], intB1[], intC1[], inti1, intj1, intk1) {
intmin_diff, current_diff, max_term;
// calculating min difference from last
// index of lists
min_diff = abs(max(A1[i1], max(B1[j1], C1[k1]))
- min(A1[i1], min(B1[j1], C1[k1])));
while(i1 != -1 && j1 != -1 && k1 != -1) {
   current_diff = abs(max(A1[i1], max(B1[j1], C1[k1]))
   - min(A1[i1], min(B1[j1], C1[k1])));
   // checking condition
   if(current_diff < min_diff)
      min_diff = current_diff;
      // calculating max term from list
      max_term = max(A1[i1], max(B1[j1], C1[k1]));
      if(A1[i1] == max_term)
         i1 -= 1;
      elseif(B1[j1] == max_term)
         j1 -= 1;
      else
         k1 -= 1;
   }
   returnmin_diff;
}
intmain() {
   intD1[] = { 5, 8, 10, 15 };
   intE1[] = { 6, 9, 15, 78, 89 };
   intF1[] = { 2, 3, 6, 6, 8, 8, 10 };
   intnD = sizeof(D1) / sizeof(D1[0]);
   intnE = sizeof(E1) / sizeof(E1[0]);
   intnF = sizeof(F1) / sizeof(F1[0]);
   cout << solve(D1, E1, F1, nD-1, nE-1, nF-1);
   return0;
}

출력

1