1655の真ん中のところを言います.

2515 ワード
boj テキストリンク

質問リンク


https://www.acmicpc.net/problem/1655

に答える


最大のお尻、最小のお尻を発表します.l(左)、r(右)というお尻を発表しました.lは中間値より低い値を格納するので、rは中間値を超える値を格納する.順番に1つの数を受け入れて、lは1つ、rは1つ、更にlは1つ、rは1つ...順番に押す.この場合、左側には中間値以下の値が含まれる必要があるため、l.top()がr.topより大きい場合は、2つの値を変更する必要があります.このようにl.top()を保存して出力すればよい.(l.top()は、常に中間値以下の最大値を格納します.)
あるいは、別の方法は、新しく得られた値がl.top()より大きい場合、rにプッシュし、lとrのサイズを比較し、l.size()がr.size()より常に大きいか等しいかを調整することである.(l.top()値をrに入れ、l.pop()または逆も同様にして、l.top()値を出力し続けることができる.

C++コード

#include <iostream>
#include <queue>
#define endl '\n'

using namespace std;

priority_queue<int> l;
priority_queue<int, vector<int>, greater<int>> r;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int N; cin>>N;
    for(int i=0; i<N; i++){
    	int num;
    	cin>>num;
    	if(l.size() == r.size()){
    		l.push(num);
    		if(!r.empty() && l.top()>r.top()){
    			int tmp = l.top();
				l.pop();
				l.push(r.top());
				r.pop();
				r.push(tmp);
			}
		}
		else{
			r.push(num);
			if(l.top()>r.top()){
    			int tmp = l.top();
				l.pop();
				l.push(r.top());
				r.pop();
				r.push(tmp);
			}
		}
		cout<<l.top()<<endl;
	}
    
    return 0;
}
[Swift] function
Programers:文字列圧縮(2020 KAKAO BLIND RECRUITMENT)