PAST3J
from 第三回 アルゴリズム実技検定
PAST3J
流れてくる数値が今まで取ったどれよりも大きい時だけ取るエージェントが複数並んでる時に、どの数値を誰が取るか答える問題。
エージェントごとに「これ以上なら取る」という数値を持っていて、「流れてきた数値xよりも小さい値の最も左のエージェント」を返せば良い。
つまりこれはソート済み配列からの効率良い探索。
二分探索の方法をPythonで調べたら標準ライブラリにbisectってのがあったので初めて使った。
pythonfrom bisect import bisect_right
N, M = [int(x) for x in input().split()]
XS = [int(x) for x in input().split()]
scores = [0] * N
for x in XS:
# need to nagate to keep asc. order
# print("come", x)
i = bisect_right(scores, -x)
if i == N:
print(-1)
else:
print(i + 1)
scores[i] = -x
# print(scores)Related Pages
- →abc168×第三回 アルゴリズム実技検定×abc169×abc173×僕のatcoderの学び方(〜緑)×arc106×僕のatcoderの学び方(〜水色)×abc183×abc187×僕のatcoderの学び方(〜青)→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]