中心値を求める

白準2696号：中心値を求めます

アイデア

最大お尻、最低お尻は1つずつ用意します.
1.最大お尻に要素を押します.
2.次の要素から開始し、最大臀部の上部の要素より大きい場合は、最小臀部に押すか、最大臀部に押す.
3、2つの要素を挿入した後、最小hip要素の個数が最大hip要素の個数より大きいまで、各hipにpop、pushを挿入する.
4.最小臀部上部の要素を出力します.

コード#コード#

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int M, x;
        priority_queue<int> pqM; //max
        priority_queue<int, vector<int>, greater<int>> pqm; //min
        
        cin >> M;
        cout << M/2+1 << '\n';
        cin >> x;
        pqM.push(x);
        cout << x << ' ';
        
        for (int i = 1; i < M; i++) {
            cin >> x;
            if (x > pqM.top()) pqm.push(x);
            else pqM.push(x);
            
            if (i%2 == 0) {
                if (pqM.size() >= pqm.size()) {
                    while (pqm.size()-pqM.size() != 1) {
                        pqm.push(pqM.top());
                        pqM.pop();
                    }
                }
                else {
                    while (pqm.size()-pqM.size() != 1) {
                        pqM.push(pqm.top());
                        pqm.pop();
                    }
                }
                if (i%20 == 0) cout << '\n';
                cout << pqm.top() << ' ';
            }
        }
        cout << '\n';
    }
    return 0;
}

おしゃべり

これは鐘万北で見た問題のようだ.優先順位Q練習の良い問題