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

Идея: блоки имеет смысл класть только в “впадины”.

Пусть высота ступеньки $x$, а у соседей $L$ и $R$.

• Если $x < L$ и $x < R$, то при увеличении $x$ на 1 оба перепада $|L-x|$ и $|R-x|$ уменьшаются на 1 ⇒ сложность уменьшается на 2.
• Если $x$ между $L$ и $R$, то один перепад уменьшается на 1, другой увеличивается на 1 ⇒ суммарно 0.
• Если $x >$ хотя бы одного соседа, то при поднятии сложность растёт.

Значит, выгодно поднимать только локальные минимумы (включая “плато” одинаковой высоты).
Если есть подряд одинаковые высоты, их можно “сжать” в один сегмент длины len: чтобы поднять такое плато на 1 метр, нужно len блоков, а выигрыш по сложности всё равно 2 (уменьшаются только два граничных перепада).

Тогда каждый локальный минимум-сегмент даёт:

• цена за +1 метр: len блоков
• выигрыш: 2

То есть выгоднее всего поднимать минимум с минимальным len. Пока его высота не дошла до меньшего из двух соседей, “цена/польза” не меняется, поэтому можно сразу поднимать его до ближайшего “упора” (или пока не кончатся блоки). Когда высоты сравнялись — сегменты сливаются.

Реализация: двусвязный список сегментов по кругу + приоритетная очередь локальных минимумов по len.

---

C++ (O(N log N), память O(N))

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

struct Item {
    long long w;   // длина сегмента (сколько блоков на +1 метр)
    int id;
    long long h;   // снимок текущей высоты (для отсева устаревших записей)
};

struct Cmp {
    bool operator()(const Item& a, const Item& b) const {
        if (a.w != b.w) return a.w > b.w;   // min-heap по w
        return a.id > b.id;
    }
};

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

    int N;
    long long K;
    cin >> N >> K;
    vector<long long> h;
    vector<long long> w;
    h.reserve(N);
    w.reserve(N);

    // Сжимаем подряд идущие равные высоты в сегменты
    for (int i = 0; i < N; ++i) {
        long long a;
        cin >> a;
        if (h.empty() || h.back() != a) {
            h.push_back(a);
            w.push_back(1);
        } else {
            ++w.back();
        }
    }
    // Учитываем круг: если первый и последний сегменты одной высоты — сливаем
    if (h.size() > 1 && h.front() == h.back()) {
        w.front() += w.back();
        h.pop_back();
        w.pop_back();
    }

    int m = (int)h.size();
    if (m == 1) { // уже ровно, сложность 0, уменьшить нельзя
        cout << 0 << "\n";
        return 0;
    }

    // Круговой двусвязный список сегментов
    vector<int> prv(m), nxt(m);
    vector<char> alive(m, 1);
    for (int i = 0; i < m; ++i) {
        prv[i] = (i - 1 + m) % m;
        nxt[i] = (i + 1) % m;
    }
    int aliveCnt = m;

    auto isMin = [&](int i) -> bool {
        if (!alive[i] || aliveCnt == 1) return false;
        int L = prv[i], R = nxt[i];
        return alive[L] && alive[R] && 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({w[i], i, h[i]});

    long long reduction = 0;

    while (K > 0 && !pq.empty() && aliveCnt > 1) {
        Item cur = pq.top(); pq.pop();
        int v = cur.id;

        if (!alive[v]) continue;
        if (h[v] != cur.h || w[v] != cur.w) continue; // устарело
        if (!isMin(v)) continue;

        long long costPerMeter = w[v];
        long long maxRaise = K / costPerMeter;
        if (maxRaise == 0) break; // даже +1 метр на самый дешёвый минимум не хватает

        int L = prv[v], R = nxt[v];
        long long target = min(h[L], h[R]);
        long long delta = target - h[v];
        if (delta <= 0) continue; // на всякий случай

        long long t = min(delta, maxRaise);
        h[v] += t;
        K -= t * costPerMeter;
        reduction += 2 * t;

        if (t < delta || K == 0) break; // блоки кончились

        // Сливаем с соседями той же высоты
        bool merged = true;
        while (merged && aliveCnt > 1) {
            merged = false;

            int p = prv[v];
            if (alive[p] && h[p] == h[v]) {
                w[v] += w[p];
                int pp = prv[p];
                prv[v] = pp;
                nxt[pp] = v;
                alive[p] = 0;
                --aliveCnt;
                merged = true;
                if (aliveCnt == 1) break;
            }

            int q = nxt[v];
            if (aliveCnt > 1 && alive[q] && h[q] == h[v]) {
                w[v] += w[q];
                int qq = nxt[q];
                nxt[v] = qq;
                prv[qq] = v;
                alive[q] = 0;
                --aliveCnt;
                merged = true;
                if (aliveCnt == 1) break;
            }
        }

        if (aliveCnt == 1) break;

        // Переоценить минимумность могли только v и его новые соседи
        for (int x : {v, prv[v], nxt[v]})
            if (isMin(x)) pq.push({w[x], x, h[x]});
    }

    cout << reduction << "\n";
    return 0;
}

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