Phần tử tối thiểu hóa tổng khoảng cách tuyệt đối trong C

Tìm x sao cho Σ|a[i] - x| nhỏ nhất. Giải pháp: x = median của mảng.

Ví dụ

Mảng: {1, 3, 9, 6, 3} → Sắp xếp: {1, 3, 3, 6, 9} → Median = 3

Tổng = |1-3|+|3-3|+|9-3|+|6-3|+|3-3| = 2+0+6+3+0 = 11

Chương trình

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int minAbsSum(int arr[], int n) {
    sort(arr, arr + n);
    int med = arr[n/2];
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += abs(arr[i] - med);
    return sum;
}

int main() {
    int arr[] = {1, 3, 9, 6, 3};
    int n = 5;
    cout << "Tong toi thieu = " << minAbsSum(arr, n);
    return 0;
}

Kết quả

Tong toi thieu = 11