Advertisement
nq1s788

Untitled

Sep 19th, 2024
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.34 KB | None | 0 0
  1. Эта задача подразумевалась на алгоритм бинарного поиска.
  2. Про бинарный поиск можно почитать здесь -- https://algorithmica.org/tg/binary-search
  3. Так же хорошее видео -- https://www.youtube.com/watch?v=uHdS2LA-yn8
  4.  
  5. Пройдемся по элементам массива b, положим текущий элемент массива b в x. Для каждого элемента бинарным поиском будем искать первый >= из a. Пусть сейчас мы смотрим на a[i]. Если a[i] <= x, тогда первый больший x будет лежать справа от i (тк массив a отсортирован изначально), если же Если a[i] > x, то стоит посмотреть слева от него -- вдруг у нас найдется другой элемент, который тоже подойдет, но будет раньше.
  6.  
  7. Пример кода на python:
  8. n, m = map(int, input().split())
  9. a = list(map(int, input().split()))
  10. b = list(map(int, input().split()))
  11. l = -1
  12. r = n
  13. for x in b:
  14.     l = -1
  15.     r = n
  16.     while (r - l) > 1:
  17.         m = (r + l) // 2
  18.         if a[m] <= x:
  19.             l = m
  20.         else:
  21.             r = m
  22.     if r == n:
  23.         print(-1, end=' ')
  24.     else:
  25.         print(r, end=' ')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement