C++에서 동일한 배열에 K개의 요소를 추가한 후 주어진 배열의 중앙값을 최대화합니다.

문제 설명

N 요소의 배열 arr[]와 K

입력 배열이 {1, 3, 2, 5}이고 k =3이면 −

• 정렬된 배열은 {1, 2, 3, 5}가 됩니다.
• 5보다 큰 3개의 요소를 삽입합니다. 이 연산 후에 배열은 {1, 2, 3, 5, 6, 6, 6}이 됩니다.
• 새 배열의 중앙값은 5입니다.

알고리즘

1. In order to maximize the median of the resultant array, all the elements that need to be inserted must be greater than the maximum element from the array
2. Sort the array and the median of the array will be arr[size / 2] if the size is odd else (arr[(size / 2) – 1] + arr[size / 2]) / 2

예시

#include <bits/stdc++.h>
using namespace std;
double getMaxMedian(int *arr, int n, int k){
   int newSize = n + k;
   double median;
   sort(arr, arr + n);
   if (newSize % 2 == 0) {
      median = (arr[(newSize / 2) - 1] + arr[newSize / 2]) / 2;
      return median;
   }
   median = arr[newSize / 2];
   return median;
}
int main(){
   int arr[] = {1, 3, 2, 5};
   int n = sizeof(arr) / sizeof(arr[0]);
   int k = 3;
   cout << "Max median = " << getMaxMedian(arr, n, k) << endl;
   return 0;
}

출력

위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다.

Max median = 5