货仓选址

AcWing-104-货仓选址

分析

见《进阶指南》第33页。

实现

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

typedef long long LL;
const int N = 100010;
int n, a[N];

int main () {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);

    sort(a + 1, a + n + 1);
    int pos;
    if (n % 2 == 0)
        pos = a[n / 2];
    else
        pos = a[n / 2 + 1];
    LL res = 0;
    for (int i = 1; i <= n; ++ i)
        res += abs(a[i] - pos);
    printf("%lld", res);
    return 0;
}