【贪心】C_018 货仓选址（排序 + 中位数）一、题目描述二、题解

一、题目描述

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

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

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

输入格式

• 第一行输入整数N。
• 第二行N个整数A1~AN。

输出格式

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

数据范围

• 1≤N≤100000

输入样例：
4
6 2 9 1
输出样例：
12

二、题解

方法一：排序 +中位数

• 假设商店分布在区间 [0, N] 中，仓库坐标为 x。
  • 若果 x 分布在 区间的左边或右边，那么总距离值一定最长。
  • 若果 x 分布在 区间的内部，那么总距离值比前者短。
• 如果是商店是奇数个，那么 x 应该建立在最中间的商店处。
• 如果是商店是偶数个，那么 x 应该建立在最中间的 2 个商店中间。

import java.util.*;
import java.math.*;
import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException {  
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        BufferedWriter w = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = sc.nextInt();
		int[] arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
		}
		Arrays.sort(arr);
		int min = 0, mid = N >>> 1;
		
		for (int i = 0; i < N; i++) {
			min += Math.abs(arr[mid]-arr[i]);
		}
		System.out.println(min);
    }
}

复杂度分析

• 时间复杂度：$O(nlogn)$，
• 空间复杂度：$O(n)$，

最后

以上就是大力鸭子为你收集整理的【贪心】C_018 货仓选址（排序 + 中位数）一、题目描述二、题解的全部内容，希望文章能够帮你解决【贪心】C_018 货仓选址（排序 + 中位数）一、题目描述二、题解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。