中位数

详见百度百科 https://baike.baidu.com/item/%E4%B8%AD%E4%BD%8D%E6%95%B0/3087401?fr=aladdin

原题：2817. 分金币

模型

前缀和

中位数

给定数轴上n个点，找出一个到他们距离之和尽量小的点

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
typedef long long LL;
int n, a[N], c[N];

int main() {
    scanf("%d", &n);
    LL sum = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        sum += a[i];
    }
    LL m = sum / n;
    c[0] = 0;
    for (int i = 1; i < n; i++) {
        c[i] = c[i - 1] + a[i] - m;
    }
    sort(c, c + n);
    LL ans = 0;
    for (int i = 0; i < n; i++) {
        ans += abs(c[i] - c[n/2]);
    }
    cout << ans << endl;
    return 0;
}

基础题：104. 货仓选址

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int n, a[N];

int main() {
    scanf("%d", &n);
    for (int i =0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    sort(a, a + n);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += abs(a[i] - a[n >> 1]);
    }
    cout << ans << endl;
    return 0;
}