算法1

闫总的算法，只是把count替换为find以保证不TLE。 我只是加了一个图便于理解。

C++ 代码

typedef long long LL;
class MKAverage {
public:
   struct Range {
       multiset<int> s;
       LL sum = 0;
       void insert(int x) {
           s.insert(x);
           sum += x;
       }
       void remove(int x) {
           s.erase(s.find(x));
           sum -= x;
       }
   }L, M, R;
   int m, k;
   vector<int> q;
    MKAverage(int _m, int _k) {
        m = _m, k = _k;
    }

    void addElement(int num) {
        q.push_back(num);
        const int n = q.size();
        if (n < m) return;
        if (n == m) {
            vector<int> qq = q;
            sort(qq.begin(), qq.end());
            for (int i = 0; i < k; ++i)L.insert(qq[i]);
            for (int i = k; i < m-k; ++i)M.insert(qq[i]);
            for (int i = m - k; i < m; ++i)R.insert(qq[i]);
        }
        if (n > m) {
            // insert to middle, so the middel will have an extra element after insertation.
            // we need delete the left most element in q with index of n - m 
            M.insert(num);
            int x = *L.s.rbegin(), y = *M.s.begin();
            if (x > y) {
                L.remove(x); M.remove(y);
                L.insert(y); M.insert(x);
            }
            x = *M.s.rbegin(), y = *R.s.begin();
            if (x > y) {
                M.remove(x); R.remove(y);
                M.insert(y); R.insert(x);
            }
            auto invalid = q[n-m-1];
            if (M.s.find(invalid) != M.s.end()) {
                M.remove(invalid);
            }
            else if (L.s.find(invalid)!=L.s.end()) {
                L.remove(invalid);
                x = *M.s.begin();
                L.insert(x), M.remove(x);
            } else {
                R.remove(invalid);
                x = *M.s.rbegin();
                R.insert(x), M.remove(x);
            }
        }
    }

    int calculateMKAverage() {
        if (q.size() < m) return -1;
        return M.sum / M.s.size();
}
};
/**
 * Your MKAverage object will be instantiated and called as such:
 * MKAverage* obj = new MKAverage(m, k);
 * obj->addElement(num);
 * int param_2 = obj->calculateMKAverage();
 */