貨艙選址
題目來源：《演算法競賽進階指南》
時間限制：1000ms 記憶體限制：64mb
題目描述
在一條數軸上有 N 家商店，它們的坐標分別為 A1~AN，
現在需要在數軸上建立一家貨倉，每天清晨，從貨倉到每家商店都要運送一車商品，
為了提高效率，求把貨倉建在何處，可以使得貨倉到每家商店的距離之和最小，
輸入格式
第一行輸入整數N，
第二行N個整數A1~AN，
輸出格式
輸出一個整數，表示距離之和的最小值，
資料范圍
1 ≤ N ≤ 100000
0 ≤ Ai ≤ 40000
樣例輸入
4
6 2 9 1
樣例輸出
12
解題思路
在數軸上選一個點，到其他點距離最短，一定是中位數的點到其他點最短，
當中位數有2個時，任意取一個即可，
因此，直接將輸入的陣列排序，然后取中位數（排序后下標為(n-1/2)的數），再算出距離即可，
解題代碼-Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = input.nextInt();
}
input.close();
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);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/249389.html
標籤：其他