[python]白駿19638センチと魔法ハンマー(Heapq)

📌 質問する

森蒂は魔法の道具を持って旅行するのが好きな悪党だ.
巨人国に到着した森蒂は、自分より背が高い巨人や同じ巨人が好きではない.
センチメートルから出る魔法の道具は魔法のハンマーで、このハンマーに当たった人の身長はハンマーに当たった人の身長になります.しかし、身長が1だとこれ以上減らないので、ハンマーの影響は受けません.
しかし魔法のハンマーには回数制限があります.そのため、森蒂は魔法のハンマーを有効に使う策略を制定した.毎回最大の巨人の一人だ.
センチメートルの戦略に従って魔法のハンマーを使えば、巨人の国のすべての巨人はセンチメートルより低いことができますか?

入力

1行目はセンチメートル以外の巨人国の人口N(1≦N≦105)とセンチメートルの身長を表す整数Hcenti(1≦Hcenti≦2)である.× 109)、魔法ハンマーの回数制限T(1≦T≦105)間隔スペース.
1つの整数H(1≦H≦2)は、それぞれの巨人の身長を表し、2行目からのN行を表す.× 109).

しゅつりょく

センチメートルの戦略として魔法ハンマーを使用し、巨人国のすべての巨人がセンチメートルよりも低いことができれば、1行目の出力はYES、2行目の出力は魔法ハンマーを使用する回数を最小限に抑えることができます.
魔法ハンマーをセンチメートルの策略に従って残りの回数を使用して、もし巨人の国家がセンチメートルより高いあるいは同じ巨人があるならば、第1行はNOを出力して、第2行は魔法ハンマーを使用した後に巨人の国家の中で背の最も高い巨人の身長を出力します.

入力例1

1 10 1
20

サンプル出力1

NO
10

入力例2

2 10 3
16
32

サンプル出力2

YES
3

入力例3

2 10 3
127
8

サンプル出力3

NO
15

入力例4

1 1 100000
1

サンプル出力4

NO
1

📌 に答える

import sys, heapq
input = sys.stdin.readline

n, h, t = map(int, input().split())
giants = [-int(input()) for _ in range(n)]
heapq.heapify(giants)
cnt = 0

for i in range(t):
    if -giants[0] == 1 or -giants[0] < h:
        break
    else:
        heapq.heapreplace(giants, -(-giants[0] // 2))
        cnt += 1

if -giants[0] >= h:
    print('NO', -giants[0], sep='\n')
else:
    print('YES', cnt, sep='\n')

最初にBroutforceで解いたところタイムアウト(^ㅠ)heapqで解いたコード!
私たちの目的はすべての巨人の身長をセンチメートルより小さくすることです.
一番背の高い巨人からエアハンマーを打ち始め、センチメートルよりも小さい巨人に着いたら、エアハンマーの使用をやめてください.

heapq

Pythonが提供する優先キューモジュール.昇順に従う.
giants = [1, 2, 3, 4, 5, 6]

heapq.heapify(giants)
リスト巨人をヒップホップ

に変換

heapq.heappush(giants, 7)
要素7を対応するお尻(巨人)にプッシュする

heapq.heappop(giants)
このヒップホップ(巨人)の最小要素は

流行している.

heapq.heapreplace(giants, 7)
ヒップホップ(巨人)の最小要素をポップアップし、要素7

を放出します.

heaqp.heappushpop(giants, 7)
エレメント7を対応するお尻(巨人)に入れ、最小のエレメントを

にポップアップします.
巨人たちの身長は昇順ではなく降順に並ぶべきなので、お尻を押すときは-1でプッシュし、popのときも戻る要素-1を乗じて演算します.
(ex.仮に巨人の身長が16、32、24だとします.hip-16、-32、-24で押すとpopか巨人に近い[0]時に最小の-32が戻されますが、ここで-1に32を乗じて、私たちが望む演算(センチの身長に比べて身長反動腔など)を行えばいいのです!)

forドアはハンマー回数で回転します.

現在最大の巨人の身長は1でエアハンマーを打つことができず、センチメートル未満では任務を完了するので、エアハンマーを打つ必要はありません.→ break

現在最大の巨人の身長がセンチメートルより大きい場合は、ハンマーで身長を空洞内に跳ね返す.