ACM 10057 A mid-summer night’s dream

ACM10041進階版。
一樣是求(1)最小值的median，
但還額外求(2)median存在於序列的次數，與(3)可能是median數的個數。
median的定義，如果序列是奇數個，
median為第(n + 1) / 2，但array從0開始，
即第n / 2個element，
(2)就把(1)代入，算個數，
(3)是1。

如果是偶數，定義上為第n / 2 - 1加第n / 2，
這兩個elements的和除以2。
即這兩個element的平均數。
這次時候會有兩種情況
可能兩數相等或不相等。
(A)相等
相等時，跟奇數一樣的情況
(1)為第n / 2 - 1個element
(2)用(1)代入算個數
(3)1個。

(B)不相等
不相等時，(1)還是一樣，
因為n / 2 - 1最小。
(2)就要分別用n / 2 - 1與n / 2代入，
(3)就有趣了，雖然定義偶數時median為
n / 2 - 1與n / 2的平均數，
但是事實上，從n / 2 - 1到n / 2為止，
這些數統統都是median，
不信的話可以隨便找個數列代入，
例如2 2 5 10，
2 3 4 5都是median。
（其實按照定義median是3.5，但若要求median需為整數，
2 3 4 5都會符合median定義）
個數算法為5 - 2 + 1，
所以為[n / 2] - [n / 2 - 1] + 1。
（用中括號，表示是第XXX個的意思）

n = 1000000非常大，要用malloc或全域變數。

/* ACM 10057 A mid-summer night’s dream
 * mythnc
 * 2011/11/09 17:44:48
 * run time: 0.428
 */
#include <stdio.h>
#include <stdlib.h>

int compar(const void *, const void *);
int countm(int *, int, int);

int main(void)
{
    int n, i, mid, num;
    int *seq;

    while (scanf("%d", &n) == 1) {
        seq = (int *)malloc(sizeof(int) * n);

        for (i = 0; i < n; i++)
            scanf("%d", seq + i);

        qsort(seq, n, sizeof(int), compar);

        mid = n / 2;
        if (n % 2 == 1) /* odd */
            printf("%d %d 1\n", seq[mid], countm(seq, seq[mid], n));
        else if (seq[mid] == seq[mid - 1]) /* even if same */
            printf("%d %d 1\n", seq[mid - 1], countm(seq, seq[mid - 1], n));
        else { /* if not same */
            num = countm(seq, seq[mid - 1], n) + countm(seq, seq[mid], n);
            printf("%d %d %d\n", seq[mid - 1], num, seq[mid] - seq[mid - 1] + 1);
        }
        free(seq);
    }
    return 0;
}

/* compar: for qsort */
int compar(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

/* countm: return number of median */
int countm(int *s, int num, int n)
{
    int i, count;

    for (count = i = 0; s[i] <= num && i < n; i++)
        if (s[i] == num)
            count++;

    return count;
}