AtCoder D - 3N Numbers (Python)

本問題では優先度付きキューを使う。ソートされた状態を保ちつつ、最小値をO(1)で取得できる。最大値バージョンの優先度付きキューが使いたいときは、キューに入れる値に-1をかけて対応する。Pythonでの優先度付きキューの使い方は以下の通り。

import heapq

a = [6, 3, 2, 4, 5]
heapq.heapify(a)    # 準備

v = heapq.heappop(a)    # 最小値をヒープから取り出す

heapq.heappush(a, 123)    # ヒープに要素を追加する

f:id:peroon:20170521101829j:plain

配列aのうち、絶対に前半に含まれる最初のN個を配列Bとし、そこから右に拡大しつつ、配列内の大きい方からN個の和を差分で求めつつ記録する。同様に、絶対に後半に含まれる最後のN個を配列Cとし、そこから左に拡大しつつ、同様に記録を取る。最後にその2つの記録を使って最適な切れ目を求めればいい。