Действительно ли бинарный поиск лучше моего решения? (Google Kickstart 2020 Round B) - PullRequest
Новая
       9

Действительно ли бинарный поиск лучше моего решения? (Google Kickstart 2020 Round B)

0 голосов
/ 25 апреля 2020

Итак, я имею в виду вопрос: -

Ведро планирует совершить очень долгое путешествие по сельской местности на автобусе. Ее путешествие состоит из N автобусных маршрутов, пронумерованных от 1 до N в том порядке, в котором она должна их проехать. Сами автобусы очень быстрые, но ходят не часто. I-й автобусный маршрут курсирует только каждые Xi дней.

В частности, она может сесть на i-й автобус только в день Xi, 2Xi, 3Xi и так далее. Поскольку автобусы очень быстрые, она может сесть на несколько автобусов в один и тот же день.

Ведро должно завершить sh свое путешествие ко дню D, но она хотела бы начать путешествие как можно позже. Какой самый последний день, когда она могла сесть на первый автобус, и все еще заканчивала sh свое путешествие ко дню D?

Итак, после окончания раунда, я посмотрел на POV других программистов, и почти большинство из них использовали бинарный поиск для решения этого вопроса, однако, мое решение было действительно базовым c. 

for _ in range(int(input())):
  no_of_buses, no_of_days = list(map(int, input().split()))
  list_of_timing = list(map(int, input().split()))
  temp_test_day=0
  check_no = no_of_days
  ans=[]

  for i in list_of_timing[::-1]:
    div = int(check_no/i)
    ans.append(i*div)
    check_no=(i*div)
  print("Case #"+str(_+1)+": "+str(ans[-1]))

Итак, я в основном только что обнаружил самый высокий (по сравнению с автобусом, чтобы взять после это) кратный интервал дней, на котором ехали автобусы, и получил ответ. Извините, если мое объяснение было неверным, я - новичок ie (месяц или два) в программировании, поэтому я обратился к вам, ребята, за помощью. Может кто-нибудь объяснить, было ли мое решение лучше или хуже бинарного поиска?

(PS - Если это поможет, мой код был принят для обоих наборов тестов)

Спасибо.

О.Г. Вопрос- https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc8/00000000002d83bf

...