[Java] UVa 10041 Vito’s family

題目連結

題意:
Vito 有很多家庭成員，他希望能經常拜訪所有人
所以要在與其他人平均相距最短的地方

題目每組先告知有幾個成員
接著給定他們的直線座標
幫 Vito 選擇一個地點，並輸出與其他成員的距離總和

即若 Vito 座標為 S，成員們為 s1, s2, ...
求最小的 |S - s1| + |S - s2| + ...

解法:
求一點距離某些點的總和最小
該點會出現在這些點的中位數
而不是平均數或其他值

可以舉簡單的例子得證
-----------------------------
假設s1 = 1, s2 = 10, s3 = 10000

若為中位數，Vito = s2 = 10
距離 = 9 + 0 + 9990 = 9999

若為平均數，Vito = (1 + 10 + 10000)/3 = 3337
距離 = 3336 + 3327 + 6663 > 9999
-----------------------------
此外，若有偶數個點，Vito 可為中間兩數任一點
如:

若 Vito 為 s2
距離為: a + 0 + b + (b+c)
若 Vito 為 s3
距離為: (a+b) + b + 0 + c
結果相同

因為此題輸出整數
否則要取中間兩數的平均值當作中位數，才能得到最短距離

程式(Java):

	import java.util.*;
	public class Main {
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int T = sc.nextInt();
	while (T-- > 0) {
	int r = sc.nextInt();
	int arr[] = new int[r];
	for (int i = 0; i < r; i++)
	arr[i] = sc.nextInt();
	Arrays.sort(arr);
	int sum = 0;
	for (int i: arr)
	sum += Math.abs(arr[r/2] - i);
	System.out.println(sum);
	}
	}
	}

view raw UVa10041.java hosted with ❤ by GitHub