数据流的中值：设计和实现一种数据结构能支持两种操作，Insert(value) 和 GetMedian()。http://weibo.com/1915548291/yDD0Cmbg1

median.cc

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

template<typename T>
class MyContainer {
public:
    void insert(const T& val);
    const T& getMedian();
private:
    priority_queue<T> lowerHeap;
    priority_queue<T, vector<T>, greater<T> > higherHeap;
};

template<typename T>
void MyContainer<T>::insert(const T& val)
{
    // Put the new element into the appropriate heap
    if (lowerHeap.empty() && higherHeap.empty()) {
        lowerHeap.push(val);
        return;
    }

    if (val < lowerHeap.top()) {
        lowerHeap.push(val);
        // Balance the two heaps, if necessary
        if (lowerHeap.size() - higherHeap.size() >= 2) {
            higherHeap.push(lowerHeap.top());
            lowerHeap.pop();
        }
    } else {
        higherHeap.push(val);
        // Balance the two heaps, if necessary
        if (higherHeap.size() - lowerHeap.size() >= 2) {
            lowerHeap.push(higherHeap.top());
            higherHeap.pop();
        }
    }
}

template<typename T>
const T& MyContainer<T>::getMedian()
{
    if (lowerHeap.size() >= higherHeap.size())
        return lowerHeap.top();
    else
        return higherHeap.top();
}

int main()
{
    MyContainer<int> container;
    int sum = 0;
    int val;
    while (cin >> val) {
        container.insert(val);
        sum += container.getMedian();
    }
    cout << sum % 10000 << endl;
    return 0;
}