货仓选址

在一条数轴上有 N 家商店，它们的坐标分别为 A1~AN。

现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。

为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

输入格式
第一行输入整数N。

第二行N个整数A1~AN。

输出格式
输出一个整数，表示距离之和的最小值。

数据范围

1≤N≤100000,
0≤Ai≤40000

输入样例：

4
6 2 9 1

输出样例：

12

第一种:

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N];

int main()
{
    cin >> n;
    for (int i = 0;i < n;i++) cin >> a[i];
    sort(a,a+n);
    int res = 0;
    for(int i = 0;i < n;i++) res +=abs(a[i] - a[n/2]);
    cout << res << endl;
    return 0;
}

第二种

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N];

int main()
{
    cin >> n;
    for (int i = 0;i < n;i++) cin >> a[i];
    nth_element(a,a+n/2,a+n);
    int res = 0;
    for(int i = 0;i < n;i++) res +=abs(a[i] - a[n/2]);
    cout << res << endl;
    return 0;
}

nth_element(a,a+k,a+n):函数只是把下标为k的元素放在了正确位置，对其它元素并没有排序，当然k左边元素都小于等于它，右边元素都大于等于它，所以可以利用这个函数快速定位某个元素

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int n,N=100010;
        int[] a = new int[N];
        Scanner s = new Scanner(System.in);
        n = s.nextInt();
        for (int i = 0; i < n; i++) {
                a[i] = s.nextInt();
        }
        Arrays.sort(a,0,n);
        int res = 0;
        for (int i = 0; i < n; i++) {
            res += Math.abs(a[i]-a[n/2]);
        }

        System.out.println(res);
    }
}