Question

Новый маршрут для трекинга Сейчас самое время планировать новые трекинговые маршруты.Опишем холмистую местность массивом из n чисел. Высота i-го холма равна hi. Маршрут должен идти по k подряд идущим холмам (учитывая тот холм, с которого маршрут будет начинаться). Немолодым туристам не очень нравится, когда приходится много раз подниматься в гору — переходить с более низкого холма на более высокий.Помогите туристам определиться с выбором маршрута — напишите программу, которая отвечает на запросы о количестве переходов с более низкого холма на более высокий на данном маршруте.Входные данныеВ первой строке даны натуральные числа n, m (2≤n,m≤2⋅105) — общее количество холмов и количество запросов соответственно.Во второй строке даны n целых чисел hi(1≤hi≤105) — высоты холмов.В следующих m строках записаны пары чисел lj и rj (1≤li≤rj≤n) — запросы на количество переходов с более низкого холма на более высокий на маршруте с началом в холме lj и завершением в rj.Выходные данныеВыведите m чисел — ответы на запросы.ПримерыВвод2 32 371 22 21 1Вывод 100ОграниченияВремя выполнения: 3 секунды

Answer 1

Ответ:

n,m = map(int,input().split())

A = list(map(int,input().split()))

C = [0]*n

for i in range(1,n):

   if A[i]>A[i-1]:

       C[i] += C[i-1]+1

   else:

       C[i]=C[i-1]

for i in range(m):

   l,r = map(int,input().split())

   print(C[r-1]-C[l-1])

Answer 2

Для решения данной задачи можно использовать алгоритм динамического программирования.

1. Сначала создадим массив dp длиной n, в котором будем хранить информацию о количестве переходов с более низкого холма на более высокий для каждого холма. 2. Заполняем массив dp начиная с первого холма и до последнего, используя следующую логику: - Если текущий холм выше предыдущего, то устанавливаем количество переходов для текущего холма равным количеству переходов для предыдущего холма плюс 1. - Если текущий холм равен предыдущему, то количество переходов остается неизменным. - Если текущий холм ниже предыдущего, то количество переходов для текущего холма сбрасывается до 0, так как маршрут должен идти только вверх. 3. После заполнения массива dp мы можем отвечать на запросы, просто выводя значения элементов dp для соответствующих интервалов из запросов.

Пример реализации на языке Python:

n, m = map(int, input().split())
heights = list(map(int, input().split()))

dp = [0] * n

for i in range(1, n):
    if heights[i] > heights[i-1]:
        dp[i] = dp[i-1] + 1
    elif heights[i] < heights[i-1]:
        dp[i] = 0
    else:
        dp[i] = dp[i-1]

for _ in range(m):
    l, r = map(int, input().split())
    print(dp[r-1] - dp[l-1])

В данной реализации мы сначала считываем значения n и m, затем высоты холмов и заполняем массив dp. Затем считываем запросы и выводим ответы на них.

Время выполнения данной программы составляет O(n + m), что является достаточно эффективным решением для данной задачи с учетом ограничений.