鄰居問題
世界聞名的黑社會老大要搬到紐約來了。在那裡他有一個大家族,並且他們都住在拉瑪菲亞大道上。因為時常要拜訪所有的親戚,他想要找一間離他們最近的房子,也就是說他希望從他的家到所有的親戚的家的距離的和為最小。
他恐嚇你寫一個程式來幫助幫助他解決這個問題。
Input
輸入的第一列有一個整數代表以下有多少組測試資料。
每組測試資料一列,第一個整數 r(0 < r < 500),代表他親戚的數目。接下來的 r 個整數 s1, s2, ..., sr 為這些親戚房子的門牌號碼(0 < si <30000)。注意:有些親戚的門牌號碼會相同。
Output
對每一組測試資料,輸出從他的新家到所有的親戚的家的距離的和為最小為多少。2 個門牌號碼 si、sj 的距離為 si - sj 的絕對值。
範例輸入:
3
2 2 4
3 2 4 6
4 2 1 999 5
範例輸出:
2
4
1001
/*----- ----- ----- -----*/ //neighbor //Made by 105502555 Teemo Hsu(Synasaivaltos) //Date: 2018/03/29 /*----- ----- ----- -----*/ #include <iostream> #include <algorithm> #include <cmath> #include <vector> using namespace std; int main(void) { int n; cin >> n; vector<int> ans; while(--n>=0) { int i,sum=0; cin >> i; vector<int> s; s.resize(i); while(--i>=0) cin >> s.at(s.size()-i-1); sort(s.begin(),s.end()); for(int k=0;k<s.size()/2;sum+=abs(s.at(k)-s.at(s.size()-k-1)),k++); ans.push_back(sum); } for(int i=0;i<ans.size();cout<<ans.at(i)<<endl,i++); return 0; } |