20111109

ACM 10041 Vito's family

一開始算mean,
立刻得到WA。
滿腦子充滿問號……

結論是:要算median,
而非mean,
當資料是對稱時算average,才能用mean,
若資料是偏斜的,算average要用median。
這篇有解釋兩者的差別。
舉個例子,若資料是10 50 99 100 101,
median是99,mean是72,
最短距離分別是141跟168,
所以要用median,而不是用mean。

/* ACM 10041 Vito's family
 * mythnc
 * 2011/11/09 15:57:38
 * run time: 0.024
 */
#include <stdio.h>
#include <stdlib.h>

#define MAXR 499

int compare(const void *, const void *);

int main(void)
{
    int r[MAXR];
    int n, sum, i, median, mid;
    
    scanf("%*d");
    while (scanf("%d", &n) == 1) {
        for (i = 0; i < n; i++)
            scanf("%d", r + i);

        qsort(r, n, sizeof(int), compare);
        mid = n / 2;
        if (n % 2 == 1)
            median = r[mid];
        else
            median = (r[mid] + r[mid - 1]) / 2;
        for (sum = i = 0; i < n; i++)
            if (median < r[i])
                sum += r[i] - median;
            else
                sum += median - r[i];

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

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

沒有留言: