Tối đa hóa trung vị của mảng trong C++

Đề bài

Cho mảng arr[] kích thước N và số K (K < N). Thêm K số nguyên bất kỳ vào mảng để trung vị của mảng mới lớn nhất.

Ví dụ: arr={1,3,2,5}, K=3. Sắp xếp: {1,2,3,5}. Thêm 3 số >5 (ví dụ 6,6,6) → mảng mới {1,2,3,5,6,6,6}. Trung vị = 5 (phần tử giữa).

Thuật toán

1. Để tối đa hóa trung vị, các phần tử thêm vào phải lớn hơn max(arr).
2. Sắp xếp mảng gốc.
3. Kích thước mới = N+K. Trung vị tại chỉ số (N+K)/2 (0-based) nếu lẻ, hoặc trung bình hai phần tử giữa nếu chẵn.
4. Vì các phần tử thêm đều lớn hơn max, chúng nằm ở cuối → không ảnh hưởng đến các phần tử nhỏ hơn max. Trung vị mới = phần tử tại vị trí (N+K)/2 trong mảng gốc đã sắp xếp (nếu chỉ số < N) hoặc max(arr) (nếu chỉ số ≥ N).

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

double getMaxMedian(int* arr, int n, int k) {
    int newSize = n + k;
    sort(arr, arr + n);
    if (newSize % 2 == 0) {
        int idx1 = newSize/2 - 1;
        int idx2 = newSize/2;
        double val1 = (idx1 < n) ? arr[idx1] : arr[n-1];
        double val2 = (idx2 < n) ? arr[idx2] : arr[n-1];
        return (val1 + val2) / 2.0;
    } else {
        int idx = newSize / 2;
        return (idx < n) ? arr[idx] : arr[n-1];
    }
}

int main() {
    int arr[] = {1, 3, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout << "Trung vi lon nhat = " << getMaxMedian(arr, n, k) << endl;
    return 0;
}

Kết quả

Trung vi lon nhat = 5