立刻得到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; }
沒有留言:
張貼留言