Processing math: 100%

ei1903の競プロメモ

競プロの解説など

HOJ 1276 - Median Find

問題URL

問題概要

N 個の整数 a1,a2,,aN がある。
各整数 i (1iN) について a1,a2,,ai の中央値を小数点以下切り捨てで求めよ。

制約

  • 1N5×105
  • 0ai109

解説

優先度付きキューを 2 つ使用します。ここでは 2 つのキューを que1,que2 とします。
que1 には A の中央値以下の値が、que2 には中央値以上の値が入ってるようにします。 また、que1que2 が常に成り立つようにします。
このとき A の中央値は、A の要素​数が偶数のとき que1+que22。 奇数のとき que12 となります。

ai を追加する際に、i が奇数であれば追加後の A の要素​数は偶数です。
ai  que2 の最小値より大きいのであれば ai  que2 に追加します。 ただし、要素​数の条件を満たすようにするため、まず que2 の最小値を削除し、que1 に追加します。 その後 ai  que2 に追加します。
そうでない場合 ai  que1 に追加します。

ai を追加する際に、i が奇数であれば追加後の A の要素​数は奇数です。
ai  que1 の最大値より大きいのであれば ai  que1 に追加します。 ただし、要素​数の条件を満たすようにするため、まず que1 の最大値を削除し、que2 に追加します。 その後 ai  que1 に追加します。
そうでない場合 ai  que2 に追加します。

このようにこの問題は計算量 O(NlogN) で解くことができます。