Koios1143的筆記

UVa 10041

發表於 分類於

UVa 10041

題目

http://domen111.github.io/UVa-Easy-Viewer/?10041

有一個人要搬家到某條路上，在這條路上有許多他的親戚，他希望新家能距離所有親戚最近

給每個親戚家所在的座標，問這新房子到其他親戚家距離總和是多少

想法

首先我們要找到新家的位置，既然要距離所有親戚最近，那就是最中間的位置了(中位數)

要計算中位數，就必須先找到中間項，那麼就先將序列排序吧!如此一來就可以很快找到中間項

找到了新家的座標之後，接下來就計算到每個親戚家的距離總和即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int n, m, mid, ans, arr[505];
int main(){
	cin>>n;
	while(n--){
		ans=0;
		cin>>m;
		for(int i=0 ; i<m ; i++){
			cin>>arr[i];
		}
		sort(arr, arr+m);
		
		// 先找中間項
		if(m%2 == 0) mid = (arr[m/2] + arr[m/2-1])/2;
		else mid = arr[m/2];
		
		// 計算距離總和
		for(int i=0 ; i<m ; i++){
			ans += abs(mid - arr[i]);
		}
		cout<<ans<<"\n";
	}
	return 0;
}

時間複雜度分析

每筆測資輸入時間複雜度為 $O(m)$

每筆測資排序時間複雜度為 $O(mlogm)$

每筆測資計算距離總和時間複雜度為 $O(m)$

每筆測資總時間複雜度約為 $O(2m + mlogm)$