PAST3J
from Third Algorithm Practical Skills Test
PAST3J
The question to answer who takes which number when there are several agents in a row who only take it when the number flowing in is greater than any of those they have taken so far.
Each agent has a numerical value that it will take if it is greater than this, and it should return "the leftmost agent with a value less than the flowing numerical value x".
So this is an efficient search from a sorted array.
I looked up the bisect search method in Python and found bisect in the standard library, so I used it for the first time.
code:python
from 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)
scoresi = -x
# print(scores)
---
This page is auto-translated from /nishio/PAST3J. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.