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Решить на C++

Answer 1

Ответ:

лол вроде же несложная задачка

Объяснение:

#include <bits/stdc++.h>

using namespace std;

int main () {

   int n,m;

   cin >> n >> m;

   vector <int> a(n), p(n, 0);

   for (int i = 0; i < n; i++)

       cin >> a[i];

   if (a[0] < a[1]) p[1] = 1;

   for (int i = 2; i < n; i++) {

       if (a[i - 1] < a[i]) p[i] = 1;

       p[i] += p[i-1];

   }

   for (int i = 0; i < m; i++) {

       int l, r;

       cin >> l >> r;

       cout << p[r - 1] - p[l - 1] << endl;

   }

}

Answer 2

Для решения данной задачи на C++, вы можете воспользоваться алгоритмом, который будет подсчитывать количество переходов с более низкого холма на более высокий для каждого маршрута. Вам потребуется использовать массив для хранения количества переходов между холмами.

Вот пример кода, решающего эту задачу:

cppCopy code
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> heights(n);

    for (int i = 0; i < n; i++) {
        cin >> heights[i];
    }

    vector<int> transitions(n, 0);

    // Вычисляем количество переходов для каждого холма
    for (int i = 1; i < n; i++) {
        if (heights[i] > heights[i - 1]) {
            transitions[i] = transitions[i - 1] + 1;
        } else {
            transitions[i] = transitions[i - 1];
        }
    }

    // Обрабатываем запросы
    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        int result = transitions[r - 1] - transitions[l - 1];
        cout << result << endl;
    }

    return 0;
}

Этот код сначала считывает высоты холмов и вычисляет количество переходов для каждого холма. Затем он обрабатывает запросы и выводит количество переходов для каждого маршрута.

Просто скопируйте этот код в вашу среду разработки C++ и запустите его, чтобы решить задачу.