Задача №114301. Маршрут для трекинга

Question

Это ЛИНЕЙНЫЙ алгоритм, у меня по времени не проходит, объясните пожалуйста почему?

Сейчас самое время планировать новые трекинговые маршруты.

Опишем холмистую местность массивом из n чисел. Высота i-го холма равна hi. Маршрут должен идти по k подряд идущим холмам (учитывая тот холм, с которого маршут будет начинаться). Немолодым туристам не очень нравится, когда приходится много раз подниматься в гору - переходить с более низкого холма на более высокий.

Помогите разработать маршрут по k подряд идущим холмам слева направо, на котором количество подъемов будет минимальным. В качестве ответа требуется вывести минимальное возможное количество подъемов на таком маршруте.

Входные данные
В первой строке даны натуральные числа n и k (2≤k≤n≤2⋅105) - общее количество холмов и количество холмов в маршруте, соответственно.
Во второй строке даны n целых чисел hi (1≤hi≤105) - высоты холмов.

Напоминаем, что два числа из одной строки в языке Python можно считать так: n, m = map(int, input().split())

Выходные данные
Выведите ответ на задачу.

Примечание
В первом примере можно начать с первого, второго или третьего холма, во втором примере - с третьего холма.

Вот мои наработки: '''

n, k = map(int, input().split())
arr = list(map(int, input().split()))
min_up = 32000
upper = 0
new_list = []
help_list = arr[:k]
for i in range(1, k):
    if help_list[i - 1] < help_list[i]:
        upper += 1
if upper < min_up:
    min_up = upper
for i in range(1, n - k + 1):
    if help_list[0] < help_list[1]:
        upper -= 1
    help_list = help_list[1:]
    help_list.append(arr[i+k-1])
    if help_list[-2] < help_list[-1]:
        upper += 1
    if upper < min_up:
        min_up = upper
print(min_up)

'''

Answer 1

n, k = map(int, input().split())
arr = list(map(int, input().split()))
min_up = 3200000000
upper = 0
index_1 = 0
for i in range(k - 1):
    if arr[i + 1] > arr[i]:
        upper += 1
if upper < min_up:
    min_up = upper
for i in range(k - 1, n - 1):
    if arr[index_1] < arr[index_1 + 1]:
        upper -= 1
    if arr[i] < arr[i + 1]:
        upper += 1
    index_1 += 1
    if upper < min_up:
        min_up = upper
print(min_up)

БЛОГ НА HUSL

Задача №114301. Маршрут для трекинга

Ответы (1 шт):