優先キュー-動的中央値
Priority Queue Dynamic Median
整数のシーケンスが順番に読み取られ、読み取られた整数の数が奇数になるたびに、整数で読み取られた整数の数が出力されます。
入力フォーマット
最初の行は後続のデータセットの数を表す整数Pを入力し、次の数行は各データセットに入力されます。
各データセットの最初の行は、最初にデータセットの番号を表す整数を入力します。
次に、データセット内のデータ数を表す整数Mを入力します。Mはスペースで区切られた奇数である必要があります。
データセットの残りの行はデータセットのデータで構成され、各行には10個のデータが含まれ、最後の行にはスペースで区切られた10個未満のデータが含まれる場合があります。
出力フォーマット
データセットごとに、最初の行はデータセットの数と出力中央値の数（データ数の2桁に1を加えたもの）を表す2つの整数を出力します。a）、データはスペースで区切られます。
データセットの残りの行は出力の中央値で構成され、各行には10個のデータが含まれ、最後の行にはスペースで区切られた10個未満のデータが含まれる場合があります。
出力に空白行があってはなりません。
データ範囲
1≤P≤1000、
1≤M≤9999
入力例：
3
1 9
1 2 3 4 5 6 7 8 9
2 9
9 8 7 6 5 4 3 2 1
3 23
23 41 13 22 -3 24 -31 -11 -8 -7
3 5103 211 -311 -45 -67 -73 -81 -99
-33 24 56
サンプル出力：
15
1 2 3 4 5
2 5
9 8 7 6 5
3 12
23 23 22 22 13 3 5 5 3 -3
-7 -3
トピックの意味：
1.合計t個のデータグループがあり、各グループの最初の行には2つの数値n、mがあります。ラベルの数と入力の数を表し、mは奇数でなければなりません
2. 1からiまでの中央値を見つけます。ここで、1<= i <= m and i is an odd number, and output the label n and the median first. Number
考え：
1.質問の中央値の数は（m + 1）/ 2（m + 1）/ 2
2、2つの優先度キューを作成します。1つは降順（つまり、大きなルートヒープ）で、もう1つは昇順（つまり、小さなルートヒープ）です。
2つのキューを作成する目的は、中央値よりも大きいものと小さいものを異なるキューに格納することです。つまり、最初のi個の数値を2つの部分に分割します。
3、現在の中央値は中央値であり、現在の入力データはtmpです。tmpが中央値よりも小さい場合は、ビッグルートにtmpを追加するため、チームのトップは確実に離れています。中央値で最も近いものをステップ5にジャンプします
4. tmp> = midの場合、tmpをルートヒープに追加し、手順6にスキップします。
5.大きなルートヒープの数が小さなルートヒープより2多い場合は、中央値が大きなルートヒープの最上部であることを意味します。現在のミッドを挿入する必要があります。小さな根の山に行き、大きな根の山の上部を中央としてポップします
6. 5とは逆に、小さい根の数が大きい根の数より2多い場合は、中央値が小さい根のヒープ内にあることを意味します。現在のミッドは大きなルートパイルに挿入され、小さなルートパイルの上部はミッドと見なされます
7、特別、最初の数字は間違いなく中央値です
コード：
#include using namespace std int t,id int n,m,mid,tmp int ans[10010]/ / used to store the median int main(void) { cin >> t while(t--) { id = 1// represents the subscript of the stored median priority_queue<int,vector<int>,less<int> >g//big root heap priority_queue<int,vector<int>,greater<int> >l/ / Small root heap cin >> n >> m >> mid cout << n << ' ' << (m + 1) / 2 << endl ans[id++] = mid for(int i = 2 i <= m i++) { cin >> tmp if(tmp < mid) { g.push(tmp) if(g.size() - l.size() == 2) { l.push(mid) mid = g.top() g.pop() } } else { l.push(tmp) if(l.size() - g.size() == 2) { g.push(mid) mid = l.top() l.pop() } } if(i & 1)//When the requirement in the title is odd, we need to output a median. We only need to record the median when we are odd. ans[id++] = mid } for(int i = 1 i < id i++) cout << ans[i] if(i == id - 1 } return 0 }