Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Эта задача подразумевалась на алгоритм бинарного поиска.
- Про бинарный поиск можно почитать здесь -- https://algorithmica.org/tg/binary-search
- Так же хорошее видео -- https://www.youtube.com/watch?v=uHdS2LA-yn8
- Пройдемся по элементам массива b, положим текущий элемент массива b в x. Для каждого элемента бинарным поиском будем искать первый >= из a. Пусть сейчас мы смотрим на a[i]. Если a[i] <= x, тогда первый больший x будет лежать справа от i (тк массив a отсортирован изначально), если же Если a[i] > x, то стоит посмотреть слева от него -- вдруг у нас найдется другой элемент, который тоже подойдет, но будет раньше.
- Пример кода на python:
- n, m = map(int, input().split())
- a = list(map(int, input().split()))
- b = list(map(int, input().split()))
- l = -1
- r = n
- for x in b:
- l = -1
- r = n
- while (r - l) > 1:
- m = (r + l) // 2
- if a[m] <= x:
- l = m
- else:
- r = m
- if r == n:
- print(-1, end=' ')
- else:
- print(r, end=' ')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement