题目描述
在一条数轴上有 N 家商店,它们的坐标分别为 A1~AN。
现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。
为了提高效率,求把货仓建在何处,可以使得货仓到每家商店的距离之和最小。
/ test case
4 输入数据个数
6 2 9 1 / 具体数据
相关题目acwing 3167 lc 296
import java.util.*;
class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] nums = new int[N];
for (int i = 0; i < N; i++) nums[i] = sc.nextInt();
System.out.println(findMinDistance(nums));
}
public static int findMinDistance(int[] nums) {
Arrays.sort(nums);
int res = 0;
int mid = nums[nums.length / 2];
for (int i : nums) {
res += Math.abs(i - mid);
}
return res;
}
}
// 复杂度 nlogn
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla