Acwing 104. 货仓选址

Problem: Acwing 104. 货仓选址

思路

这是一个经典的中位数问题。在一维空间中，使得所有点到某一点的距离之和最小，那个点应该选择所有点的中位数。如果有偶数个点，那么中位数是中间两个数的平均值。

解题方法

首先，我们需要读取所有商店的位置，并将它们排序。然后，我们找到中位数。如果商店的数量是偶数，那么中位数是中间两个数的平均值。否则，中位数就是中间的那个数。最后，我们计算所有商店到中位数的距离之和。

复杂度

时间复杂度:

$O(nlogn)$，主要是排序的时间复杂度。

空间复杂度:

$O(n)$，需要存储所有商店的位置。

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
	static StreamTokenizer sr = new StreamTokenizer(in);
	static int n;
	static int MAXN = 100010;
	static int[] arr = new int[MAXN];

	public static void main(String[] args) throws IOException {
		n = nextInt();
		for (int i = 1; i <= n; i++) {
			arr[i] = nextInt();
		}
		Arrays.sort(arr, 1, n + 1);
		int x = 0;
		if (n % 2 == 0) {
			x = (arr[n / 2] + arr[n / 2 + 1]) / 2;
		} else {
			x = arr[(n + 2 - 1) / 2];
		}
		long res = 0;
		for (int i = 1; i <= n; i++) {
			res += Math.abs(arr[i] - x);
		}
		out.println(res);
		out.flush();

	}

	static int nextInt() throws IOException {
		sr.nextToken();
		return (int) sr.nval;
	}

}