白駿1655.真ん中を言う

7785 ワード
アルゴリズム#アルゴリズム# テキストリンク
白俊1655号の真ん中を教えてください。
TRYS AND INSIGHTS

  • 最大臀部の最小臀部を半分に分けて
  • 初訪問
  • まとめてみると、
  • 偶数(2 n個)=>最大ヒップ(0."n-1")/最小ヒップ(n..2n-1)
  • 奇数(2 n+1個)=>最大hip(0.n-1)/最小hip("n".2 n)
  • ここで「」は中間値に相当する.
  • 偶数個中間値]max heap[0]
  • 奇数個中間値]min heap[0]

  • 要素を追加すると

  • 偶数

  • 元素<最大臀部の根
    :最大ヒップを最小ヒップに、要素を最大ヒップに

  • 最大臀部の根<要素<最小臀部の根
    :最小ヒップ(要素=最小ヒップのルート)に要素を入れます.

  • 要素>最小臀部のルート(Elements>Min臀部のルート)
    :エレメントを最小ヒップに配置

  • 単数

  • 元素<最大臀部の根
    :最大ヒップに要素を入れる

  • 最大臀部の根<要素<最小臀部の根
    :最大ヒップ(要素=最大ヒップのルート)に要素を入れます.

  • 要素>最小臀部のルート(Elements>Min臀部のルート)
    :最小ヒップを最大ヒップに、要素を最小ヒップに

  • 再包装できなかったのが一番残念です時間があればもう一度やりたい(重複コード)
    • [1回の試行]
    ランタイムエラー:名前が間違っています.毎回印刷していますができません
    だからansリストに追加して、最後に印刷で印刷して、結果はよかったです.
    SOLUTION
    import sys
import heapq

def main():
    N = int(sys.stdin.readline())
    left = []; right = []   # left: 최대 힙, right: 최소 힙
    right.append(int(sys.stdin.readline())) # i=0
    ans = [right[0]]
    for i in range(1, N):
        # i가 지금까지 들어온 원소의 개수 -1개
        x = int(sys.stdin.readline())
        if i%2 == 0:
            # x 들어가기 전 h는 짝수개
            if x < -1*left[0]:
                left_root = -1*heapq.heappop(left)
                heapq.heappush(right, left_root)
                heapq.heappush(left, -1*x)
            else:
                heapq.heappush(right, x)
            ans.append(right[0])
        else:
            # x 들어가기 전 h는 홀수개
            if x < right[0]:
                heapq.heappush(left, -1*x)
            else:
                right_root = heapq.heappop(right)
                heapq.heappush(left, -1*right_root)
                heapq.heappush(right, x)
            ans.append(-1*left[0])

    for a in ans:
        print(a)

main()
    redisクラスタ接続プールの例
    scrapy--RedisベースのBloomfilterによる重量除去