🔗 UVA-10041

tags: `貪心(Greedy)`, `中位數貪心`

範例程式碼已於 UVA、瘋狂程設(CPE)、ZeroJudge 上皆測試通過。

題意

給定 $n$ 個數字，找出一個數字，使得所有數字與這個數字的差的總和最小，並輸出這個總和。

LuckyCat 的中文翻譯

思路：中位數貪心

中位數即為需要找的數字，說明如下：

對於 $n$ 為奇數的情況，顯然中位數到所有點的距離和最小，左移或右移都會增加距離和，這可以用畫數線的方式來證明。
若 $n$ 為偶數，則兩個中位數之間的任意數都可以是答案，同樣可以用畫數線的方式來證明。

故排序後，直接取下標 $\lfloor \frac{n}{2} \rfloor$ 的數作為中位數，再計算所有點到中位數的距離和即可。

複雜度分析

時間複雜度： $O(n\log n)$ ，排序的時間複雜度。
空間複雜度： $O(n)$ ，需要保存所有數字。

t = int(input())

for _ in range(t):
    n, *nums = list(map(int, input().split()))
    nums.sort()
    mid = nums[n//2]
    print(sum(abs(x - mid) for x in nums))

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define endl '\n'

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int t, n;
    cin >> t;
    while (t--) {
        cin >> n;
        vector<int> s(n);
        for (auto &x: s) cin >> x; // read input
        sort(s.begin(), s.end()); // sort
        int mid = n / 2;
        LL ans = 0;
        for (auto &x: s) ans += abs(x - s[mid]);
        cout << ans << endl;
    }
    return 0;
}