白駿1655号-平凡なリュックサック

問題を読み、簡単にアクセスすると、入力を受信するたびにソートし、中間値を検索して出力できます.私も、コードしやすい結果はタイムアウト...
中間値の並べ替えと検索をO(1)に設定する必要があることを認識した後,優先キューを用いて異なるデータ構造形式を考慮した.
これは、2つの優先キューを使用して入力した数値の中間値をtopに維持し、抽出する問題です.
最初に想定した方法は、優先順位キューを2つのキュー(最大スタック、最小スタック)に分けてソート状態を作成することです.
例:
入力した数字が1,2,3,4,5,6,7,8の場合
優先キュー1(最大ヒープ):4、3、2、および1
優先キュー2(minheap):5、6、7、8
として設定されたメソッド.
2つのレベルに分けられますが、優先キュー1を逆起動して、優先キュー2を反時計回りに表示すると、優先キュー1には常に中間値が1、2、3、4、5、6、7、8の順に表示されます.
論理はまず、最も大きな数の最初の数値入力を受け入れます.
minheap以上、max heap以下.
次に、max heapのtopに基づいて、新しく入力した数字をmax heapにプッシュするか、mean heapにプッシュします.
中間値が最も多くなるように、2つの優先キューの数を常に等しいか、または差が1に設定する必要があります.
優先キュー1(最大ヒープ):2 1
優先キュー2(minheap):34 5 6 8
上記の例に示すように、数を一方に偏らせてはいけません.入力した新しい数値がpushの数と同じである場合、一方の側にpushを入力し、pushキューのtopを別のキューに移動します.
2つのキューの数が異なる場合は、プッシュする前に同じキューに移動し、上記の操作を実行します.
2つの優先キューのバランスを実現し、中間値を維持します.

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

using namespace std;


int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);	
    int num;
    cin >> num;
    priority_queue<int, vector<int>, greater<int> > min_queue;
    priority_queue<int, vector<int>, less<int> > max_queue;

    int input;
    cin >> input;
    max_queue.push(input);
    cout << max_queue.top() << '\n';
    for(int i = 1; i < num; i++){
        
        cin >> input;
        
        

        if(max_queue.top() < input){
            if(max_queue.size() == min_queue.size()){
                min_queue.push(input);
                int temp = min_queue.top();
                min_queue.pop();
                max_queue.push(temp);
            }
            else{
                min_queue.push(input);
                if(max_queue.size() != min_queue.size()){
                    int temp = min_queue.top();
                    min_queue.pop();
                    max_queue.push(temp);
                }
            }
            
        }
        else{
            if(max_queue.size() == min_queue.size()){
                max_queue.push(input);
                int temp = max_queue.top();
                max_queue.pop();
                min_queue.push(temp);
            }
            else{
                max_queue.push(input);
                if(max_queue.size() != min_queue.size()){
                    int temp = max_queue.top();
                    max_queue.pop();
                    min_queue.push(temp);
                }
            }
            
        }
        if(max_queue.size() < min_queue.size()){
            cout << min_queue.top() << '\n';
        }
        else{
            cout << max_queue.top() << '\n';

        }
        
        
    }
    
}

他の人のコードリファレンス

他人のコードを見て勉強するとき、私の論理より簡単な論理があります.私が実施するとき、pushはmax heapのtopと比較して優先順位キューを選択してpushを行い、これは不要なプロセスです.最大スタックと最小スタックの数が同じである場合、最大スタックにプッシュすることによって、数が異なる場合に最小スタックにプッシュすることによって、常に2つのキューの数が同じに保たれる.△この部分は私と同じです.ただし、プッシュするキューではなく入力数のサイズを比較し、プッシュ後に2つのキューのtopを比較することで、常にmax heapのtopに小さい値を入力することができます.これは、優先順位キューにプッシュし、topを比較してmax heapに小さな値を移動するだけで、最終的な形式は私の論理と同じになります.これらの論理の条件文は、より少なく、より簡単で、より直感的だと思います.

#include <iostream>
#include <queue>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);	
    priority_queue<int , vector<int>, greater<int> > min_queue;
    priority_queue<int, vector<int>, less<int> > max_queue;

    int num;
    cin >> num;
    for(int i = 0; i < num; i++){
        int input;
        cin >> input;
        if(max_queue.size() == min_queue.size()){
            max_queue.push(input);
        }
        else{
            min_queue.push(input);
        }
        // 두 우선순위 큐가 비어있지 않으면서 max heap의 top가 min heap의 top 보다 클 경우 swap
        if(!max_queue.empty() && !min_queue.empty() && max_queue.top() > min_queue.top()){
            int swap_temp1 = max_queue.top();
            int swap_temp2 = min_queue.top();
            max_queue.pop();
            min_queue.pop();
            max_queue.push(swap_temp2);
            min_queue.push(swap_temp1);
        }
        
        cout << max_queue.top() << '\n';
    }
}

リファレンス

https://blog.naver.com/music4537/222249608344

その他

前述したように、I/Oが頻繁にn回発生する場合、endまたはcinおよびcoutを使用するとタイムアウトが発生する可能性が高い.
ios_base::sync_with_stdio(false); cin.tie(NULL);
上記の処理をドメイン内で実行することにより、I/O速度を向上させることができる.また、endではなく「n」を使用して改行を高速化します.