算法分析

• 1、把A[0]~A[N-1]排序，设货仓在X坐标处，X左侧的商店有P家，右侧的商店有Q家。若P < Q，则每把仓库的选址向右移动1单位距离，距离之和就会变少Q - P.同理，若P > Q，则仓库的选址向左移动会使距离之和变小。当P==Q时为最优解。

• 2、因此仓库应该建在中位数处，把A进行排序，

  • 当N为奇数时，货仓建在A[(N - 1)/2]处，

  • 当N为偶数时，仓库建在A[(N - 1)/2 + 1]处。

如下图举例：

时间复杂度($O(nlog(n))$)

参考文献

Java 代码

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

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] A = new int[n];
        for(int i = 0;i < n;i++) A[i] = scan.nextInt();
        Arrays.sort(A);
        int mid = (n - 1)/2;
        int sum = 0;
        for(int i = 0;i < n;i++) sum += Math.abs((A[mid] - A[i]));
        System.out.println(sum);
    }
}