---
title: 'UVa 10041 題解 — C++'
disqus: hackmd
---

# UVa 10041 題解 — C++
:::info
:bulb: 此筆記為UVa 10041的題目詳解，包含解題思路、C++範例程式碼。
:::

## Vito's family (ZeroJudge a737.)
### [題目](https://zerojudge.tw/ShowProblem?problemid=a737)
:::success
世界聞名的黑社會老大Vito Deadstone要搬到紐約來了。在那裡他有一個大家族，並且他們都住在Lamafia大道上。因為Vito時常要拜訪所有的親戚，他想要找一間離他們最近的房子，也就是說他希望從他的家到所有的親戚的家的距離的和為最小。

他恐嚇你寫一個程式來幫助幫助他解決這個問題。
:::

### 輸入 / 輸出說明
| **輸入說明** | **輸出說明** |
|:-:|:-:|
|  | 

### 解題思路
:::warning
這一題有個關鍵，就是你必須要知道由所有門牌號排序之後，這串數值的中位數與其他的所有點的距離和是最小的。

我這邊說明一下中位數的規則。
取中位數的規則：
1. 數值總個數為奇數個
=> 最中間的數值即是中位數
2. 數值總個數為偶數個
=> 最中間的兩個資料數值的平均值即是中位數
:::

### 範例程式碼

#include <bits/stdc++.h>
using namespace std;

int main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i;
	int n;
	
	cin >> n;
	
	while (n > 0) {
		int r, home, t = 0;
		
		cin >> r;
		
		int s[r];
		
		for (i=0;i<r;i++)
			cin >> s[i];
			
		sort(s, s + r);
		
		if (r % 2 == 1)
			home = s[r/2];
		else
			home = (s[r/2-1] + s[r/2]) / 2;
			
		for (i=0;i<r;i++)
			t += abs(home - s[i]);
			
		cout << t << endl;
		
		n--;
	}

	return 0;
}

### 運行結果
<font color="#00BB00">**AC**</font> (0.4s, 332KB)

###### tags: `CPE 1星`

:::danger
查看更多資訊請至：https://www.tseng-school.com/
:::