C++で配列にK個の要素を追加した後に中央値を最大化する方法

問題概要

N個の要素からなる配列 arr[] と整数 K(K < N)が与えられます。この配列に K 個の整数要素を挿入し、結果として得られる配列の中央値を最大化することが課題です。

例として、入力配列が {1, 3, 2, 5}、k = 3 の場合を考えてみましょう。

• 配列をソートすると {1, 2, 3, 5} になります
• 最大値 5 より大きい要素を 3 つ挿入します。操作後の配列は {1, 2, 3, 5, 6, 6, 6} になります
• 新しい配列の中央値は 5 となります

アルゴリズム

この問題を解くための手順は以下の通りです。

1. 結果の配列の中央値を最大化するには、挿入するすべての要素が元の配列の最大要素よりも大きくなければなりません。そうすることで、挿入した要素が中央値の位置より後ろに配置されます。
2. 配列をソートします。新しい配列のサイズが奇数の場合、中央値は arr[size / 2] となり、偶数の場合は (arr[(size / 2) - 1] + arr[size / 2]) / 2 となります。

実装例(C++)

#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

解説のポイント

このアルゴリズムの計算量は、ソート処理が支配的となるため O(N log N) です。挿入する K 個の要素はすべて最大値より大きいため、中央値の位置に影響を与えるのは元の配列の要素だけです。そのため、実際に配列へ要素を追加する必要はなく、新しいサイズ(n + k)に基づいて中央値のインデックスを計算するだけで効率的に答えを求められます。