10041 - Vito's Family

Background 

The world-known gangster Vito Deadstone is moving to New York. He has a very big family there, all of them living in Lamafia Avenue. Since he will visit all his relatives very often, he is trying to find a house close to them.

Problem 

Vito wants to minimize the total distance to all of them and has blackmailed you to write a program that solves his problem.

Input 

The input consists of several test cases. The first line contains the number of test cases.For each test case you will be given the integer number of relatives r ( 0 < r < 500) and the street numbers (also integers) where they live ( 0 < s_i < 30000 ). Note that several relatives could live in the same street number.

Output 

For each test case your program must write the minimal sum of distances from the optimal Vito's house to each one of his relatives. The distance between two street numbers s_i and s_j is d_ij= |s_i-s_j|.

Sample Input 

2
2 2 4 
3 2 4 6

Sample Output 

2
4

出處: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=982

---

題目是說Vito威脅你幫他寫一個程式(programmer好可憐，沒賺到錢還有被威脅QQ)，讓他可以算出他到所有親戚家的最短距離總和。要找出最短的距離總和，必須要先幫Vito找到一個住的地方讓他可以到親戚家的距離總和最短，這個地方其實就是所有街編號的中位數，所以我們只要找到所有街編號的中位數，就可以算出最短距離總和。所以首先第一步，就是要將所有街的編號做排序，再找中位數。若街的數量是奇數，中位數當然就是中間的數字;若街的數量是偶數，則中位數就是中間兩個數相加除以2。但是在這題，偶數的情況可以取中間兩個數前面那個數或後面那個數都可以，並不會影響答案。最後再將所有的街編號和中位數相減取絕對值加總就可以得到答案。

以下是c++程式碼:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;

int main() {
    int n;

    cin >> n;
    while (n--) {
        int r;
        vector<int> streets;
        int mid;
        int sum = 0;

        cin >> r;
        while (r--) {
            int s;

            cin >> s;
            streets.push_back(s);
        }
        sort(streets.begin(), streets.end());
        mid = streets.size() / 2;
        for (int i=0; i<streets.size(); i++)
            sum += abs(streets[mid] - streets[i]);
        cout << sum << endl;
    }
    return 0;
}