Acwing 104. 货仓选址

本文主要是介绍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;}}

这篇关于Acwing 104. 货仓选址的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---