uva 10041 Vito's Family

一看到題目時，會想說把 street number 全加起來後算總共相異 street number 個數的平均，

但是取 street number 的中位數所得的 sum 會更少。

平均數為這些 street number 的中心，和左、右的 street number的差異在 +1 ~ -1 之間，但

是題目有說 "會有相同的 street number"，平均數左、右兩邊的 street number 個數不相同，

加總起來時，會因為相同的 street number，而造成差異。

中位數的兩邊的 street number 個數都一樣，即使完全相異的 street number 也可以處理。

ex: 2, 3, 10

mean : 5   =>   2, 3, 5, 10

5 向左、右兩邊走時，都要走 d(3,5), d(3,10)

median : 3 => 2, 3, 10

往右走時，會走 d(3,10)

d(3,10) < d(3,5) + d(3,10)

當數字有出現相同時，中位數的某一邊 street number 個數有可能比較多，造成 sum 增加。

因此，取中位數所得的 sum 會比較小。


#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int compare(const void* a , const void* b){
    return *(int *)a - *(int *)b;
}

int main(void){
    int amount,i;
    int relatives,streets[510],sum,median;

    scanf("%d",&amount);
    while(amount--){
        scanf("%d",&relatives);
        for(i=0;i<relatives;i++){
            scanf("%d",&streets[i]);
        }

        qsort(streets,relatives,sizeof(int),compare);

        median=streets[relatives/2];

        sum=0;
        for(i=0;i<relatives;i++){
            sum+=abs(streets[i]-median);
        }

        printf("%d\n",sum);
    }



    return 0;
}