Phần tử mảng có tổng sai số tuyệt đối tối thiểu trong C++

Bài toán tìm phần tử trong mảng sao cho tổng các sai số tuyệt đối đến các phần tử còn lại là nhỏ nhất.

Mảng (Array) – Bộ chứa các phần tử cùng kiểu, kích thước xác định trước.

Sai số tuyệt đối (Absolute difference) – Giá trị tuyệt đối của hiệu hai số (luôn dương).

Tổng sai số tuyệt đối tối thiểu của phần tử a[i]:

MinAbsDiff(a[i]) = min(|a[i] - a[j]|) với j ≠ i

Ví dụ

Input: arr = {1, 3, 9, 3, 6} Output: 8

Giải thích

Chọn x = 3 (trung vị), tổng sai số tuyệt đối:

|1-3| + |3-3| + |9-3| + |3-3| + |6-3| = 2 + 0 + 6 + 0 + 3 = 11

Lưu ý: Ví dụ gốc có vẻ thiếu phần tử 6 trong tính toán. Kết quả đúng cho mảng đã cho là 11.

Thuật toán tối ưu (sử dụng trung vị)

• Sắp xếp mảng.
• Phần tử trung vị (median) cho tổng sai số tuyệt đối tối thiểu.
• Tính tổng |a[i] - median| cho mọi i.

Chương trình C++ mẫu

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

long long minAbsSumDiff(vector<int> a) {
    sort(a.begin(), a.end());
    int n = a.size();
    int median = a[n/2];
    long long sum = 0;
    for (int x : a) sum += abs(x - median);
    return sum;
}

int main() {
    vector<int> a = {1, 3, 9, 3, 6};
    cout << "Tổng sai số tuyệt đối tối thiểu: " << minAbsSumDiff(a);
    return 0;
}

Kết quả

Tổng sai số tuyệt đối tối thiểu: 11