Реши задачу на c++ Задача C. Горная трасса Имя вхо...

Идея

Сожмём маршрут в плато: подряд идущие ступеньки одинаковой высоты заменим одним узлом со:

• h — высота плато
• len — его ширина (сколько ступенек в плато)

Тогда сложность — это сумма по границам плато.

Ключевое наблюдение:

Если плато — строгий локальный минимум (его высота меньше высот двух соседних плато), то если поднять всё это плато на 1 метр, сложность уменьшится ровно на 2 (по 1 на каждой из двух границ), а стоимость — len блоков.

Поднимать «не минимум» не даёт выигрыша (в лучшем случае 0, часто ухудшает).

Значит мы покупаем «шаги подъёма» с одинаковой выгодой +2, но разной ценой len.
Чтобы максимизировать суммарный выигрыш при бюджете k, всегда выгодно делать следующий шаг там, где он самый дешёвый, то есть у локального минимума с минимальным len.

Поднимаем выбранный минимум сразу «пачкой» до ближайшего события:

• либо до высоты меньшего из соседей (после чего плато с ним сольётся),
• либо пока не кончатся блоки.

Все операции делаем на циклическом двусвязном списке плато + priority_queue (минимальная ширина).

Сложность: O(n log n) по числу плато (≤ n), память O(n).

---

Решение на C++ (C++17)

cpp
#include <bits/stdc++.h>
using namespace std;

struct FastScanner {
    static constexpr size_t BUFSIZE = 1 << 20;
    int idx = 0, size = 0;
    char buf[BUFSIZE];

    inline char readChar() {
        if (idx >= size) {
            size = (int)fread(buf, 1, BUFSIZE, stdin);
            idx = 0;
            if (size == 0) return 0;
        }
        return buf[idx++];
    }

    template<typename T>
    bool readInt(T &out) {
        char c;
        do {
            c = readChar();
            if (!c) return false;
        } while (c <= ' ');

        bool neg = false;
        if (c == '-') { neg = true; c = readChar(); }

        T val = 0;
        while (c > ' ') {
            val = val * 10 + (c - '0');
            c = readChar();
        }
        out = neg ? -val : val;
        return true;
    }
};

struct Item {
    long long len;
    int id;
    int ver;
};
struct Cmp {
    bool operator()(const Item& a, const Item& b) const {
        if (a.len != b.len) return a.len > b.len; // min-heap by len
        return a.id > b.id;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    FastScanner fs;
    int N;
    long long K;
    if (!fs.readInt(N)) return 0;
    fs.readInt(K);

    vector<long long> a(N);
    for (int i = 0; i < N; i++) fs.readInt(a[i]);

    // initial difficulty
    long long D0 = 0;
    for (int i = 0; i < N; i++) {
        long long x = a[i];
        long long y = a[(i + 1) % N];
        D0 += llabs(x - y);
    }
    if (D0 == 0) {
        cout << 0 << "\n";
        return 0;
    }

    // compress into plateaus
    vector<long long> h;
    vector<long long> len;
    h.reserve(N);
    len.reserve(N);

    for (int i = 0; i < N; i++) {
        if (h.empty() || a[i] != h.back()) {
            h.push_back(a[i]);
            len.push_back(1);
        } else {
            len.back()++;
        }
    }
    // merge first and last if equal (cycle)
    if (h.size() > 1 && h.front() == h.back()) {
        len[0] += len.back();
        h.pop_back();
        len.pop_back();
    }

    int M = (int)h.size();
    if (M == 1) {
        cout << 0 << "\n";
        return 0;
    }

    vector<int> prv(M), nxt(M), ver(M, 0);
    vector<char> alive(M, 1);

    for (int i = 0; i < M; i++) {
        prv[i] = (i - 1 + M) % M;
        nxt[i] = (i + 1) % M;
    }

    auto isMin = [&](int i) -> bool {
        if (!alive[i]) return false;
        int L = prv[i], R = nxt[i];
        return h[i] < h[L] && h[i] < h[R];
    };

    priority_queue<Item, vector<Item>, Cmp> pq;
    for (int i = 0; i < M; i++) {
        if (isMin(i)) pq.push({len[i], i, ver[i]});
    }

    long long reduction = 0;
    int active = M;

    auto kill = [&](int j) {
        alive[j] = 0;
        ver[j]++;
        active--;
    };

    while (K > 0 && active > 1 && !pq.empty()) {
        Item it = pq.top(); pq.pop();
        int i = it.id;
        if (!alive[i] || it.ver != ver[i] || it.len != len[i] || !isMin(i)) continue;

        long long s = len[i];
        if (s > K) break; // cheapest step is not affordable => nothing else is

        int L = prv[i], R = nxt[i];
        long long target = min(h[L], h[R]);
        long long delta = target - h[i]; // >= 1 for strict local min

        long long t = min(delta, K / s);
        if (t == 0) break;

        h[i] += t;
        K -= s * t;
        reduction += 2 * t;

        if (t < delta) break; // budget ended, and s is minimal => can't do more anywhere

        // reached target, merge with neighbor(s) with same height
        L = prv[i];
        R = nxt[i];

        if (L == R) {
            // only two nodes in the cycle
            if (alive[L] && h[L] == h[i]) {
                len[i] += len[L];
                kill(L);
                prv[i] = i;
                nxt[i] = i;
            }
        } else {
            if (alive[L] && h[L] == h[i]) {
                len[i] += len[L];
                int pL = prv[L];
                prv[i] = pL;
                nxt[pL] = i;
                kill(L);
            }
            R = nxt[i];
            if (R != i && alive[R] && h[R] == h[i]) {
                len[i] += len[R];
                int nR = nxt[R];
                nxt[i] = nR;
                prv[nR] = i;
                kill(R);
            }
        }

        ver[i]++;

        // re-check local minima among affected nodes
        int A = i, B = prv[i], C = nxt[i];
        if (alive[A] && isMin(A)) pq.push({len[A], A, ver[A]});
        if (alive[B] && isMin(B)) pq.push({len[B], B, ver[B]});
        if (alive[C] && isMin(C)) pq.push({len[C], C, ver[C]});
    }

    // reduction can't exceed initial difficulty, but algorithm won't overshoot
    if (reduction > D0) reduction = D0;
    cout << reduction << "\n";
    return 0;
}

---

Если хочешь, могу кратко пояснить на одном твоём примере по шагам (какие плато считаются минимумами, сколько поднимаем, где сливаем).