Zerojudge d713：中位数

Zerojudge d713：中位数

題目大意：求數列中位數。

解法：$\text{heap}$。

$\text{Code：}$可用 $\text{priority_queue}$，只是我沒用。

#pragma GCC optimize("O3")
#include <iostream>
#define gu() getchar_unlocked()
#define pu(X) putchar_unlocked(X)
#define LL long long
#define SWAP(X,Y) X^=Y,Y^=X,X^=Y
using namespace std;

bool pause = 0;

int in() {
    int a = 0;
    char c = gu();
    bool sml = 0;
    while (c == ' ' || c == '\n') {
        c = gu();
    }
    if (c == EOF) {
        pause = 1;
        return 0;
    }
    if (c == '-') {
        sml = 1;
        c = gu();
    }
    while (c >= '0' && c <= '9') {
        a = a * 10 + c - '0', c = gu();
    }
    return sml ? -a : a;
}

void out (int x) {
    if (x < 0) {
        x = -x, pu ('-');
    }
    string str;
    do {
        str = (char) (x % 10 + '0') + str;
        x /= 10;
    } while (x);
    for (int i = 0; i < str.length(); i++) {
        pu (str[i]);
    }
    pu ('\n');
}

int max_heap[100005], min_heap[100005];
int num, pos_max = 0, pos_min = 0;

void up_heap_max (int now) {
    if (now == 0) {
        return;
    }
    int to = (now - 1) / 2;
    if (max_heap[to] < max_heap[now]) {
        SWAP (max_heap[to], max_heap[now]);
        up_heap_max (to);
    }
}

void up_heap_min (int now) {
    if (now == 0) {
        return;
    }
    int to = (now - 1) / 2;
    if (min_heap[to] > min_heap[now]) {
        SWAP (min_heap[to], min_heap[now]);
        up_heap_min (to);
    }
}

void max_heapify (int now) {
    int left = now * 2 + 1, right = now * 2 + 2;
    int big = max_heap[now];
    if (left < pos_max && max_heap[left] > big) {
        big = max_heap[left];
    }
    if (right < pos_max && max_heap[right] > big) {
        big = max_heap[right];
    }
    if (big == max_heap[now]) {
        return;
    }
    if (big == max_heap[left]) {
        SWAP (max_heap[now], max_heap[left]);
        max_heapify (left);
    } else {
        SWAP (max_heap[now], max_heap[right]);
        max_heapify (right);
    }
}

void min_heapify (int now) {
    int left = now * 2 + 1, right = now * 2 + 2;
    int sml = min_heap[now];
    if (left < pos_min && min_heap[left] < sml) {
        sml = min_heap[left];
    }
    if (right < pos_min && min_heap[right] < sml) {
        sml = min_heap[right];
    }
    if (sml == min_heap[now]) {
        return;
    }
    if (sml == min_heap[left]) {
        SWAP (min_heap[now], min_heap[left]);
        min_heapify (left);
    } else {
        SWAP (min_heap[now], min_heap[right]);
        min_heapify (right);
    }
}


int len (LL n) {
    int re = 0;
    if (n < 0)
        re++, n = -n;
    do {
        re++;
        n /= 10;
    } while (n);
    return re;
}

void solve() {
    if (pos_max == 0) {
        out (num);
        max_heap[pos_max++] = num;
        return;
    }
    if (pos_min == 0) {
        out ( ( (LL) num + max_heap[0]) / 2);
        min_heap[pos_min++] = num;
        if (max_heap[0] > min_heap[0]) {
            SWAP (max_heap[0], min_heap[0]);
        }
        return;
    }
    if (pos_max == pos_min) {
        if (num <= max_heap[0]) {
            max_heap[pos_max] = num;
            up_heap_max (pos_max);
        } else if (max_heap[0] < num && num <= min_heap[0]) {
            max_heap[pos_max] = max_heap[0];
            max_heap[0] = num;
            up_heap_max (pos_max);
        } else {
            max_heap[pos_max] = max_heap[0];
            max_heap[0] = min_heap[0];
            up_heap_max (pos_max);
            min_heap[0] = num;
            min_heapify (0);
        }
        pos_max++;
        out (max_heap[0]);
    } else {
        if (num >= min_heap[0]) {
            min_heap[pos_min] = num;
            up_heap_min (pos_min);
        } else if (max_heap[0] <= num && num < min_heap[0]) {
            min_heap[pos_min] = min_heap[0];
            min_heap[0] = num;
            up_heap_min (pos_min);
        } else {
            min_heap[pos_min] = min_heap[0];
            min_heap[0] = max_heap[0];
            up_heap_min (pos_min);
            max_heap[0] = num;
            max_heapify (0);
        }
        pos_min++;
        out ( ( (LL) max_heap[0] + min_heap[0]) / 2);
    }
}

int main() {
    while (1) {
        num = in();
        if (pause) {
            return 0;
        }
        solve();
    }
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！