Пірамідальний масив#12322

Пірамідальний масив (Розбір)

Автор задачі:	Ігор Мельникович (Melnykovych_Ihor)
Підготував:	Ігор Мельникович (Melnykovych_Ihor)
Аналіз:	Андрій Холод (Connect)

Розв’язання

Ключова ідея: максимум піраміди

Позначимо $m x = max (a)$ mx = \max(a). У будь-якій піраміді максимум — це деяке значення $H$ і всі числа $1.. H - 1$ 1..H-1 мають з’явитися по обидва боки від максимуму.

Оскільки ми можемо лише вставляти 1 та збільшувати, то зменшувати елементи не можна. Тому природно будувати піраміду висотою не меншою за поточний максимум, і в оптимальному розв’язку (для цієї реалізації) розглядається основний випадок $H = m x$ H = mx.

Нехай всі позиції з максимальним значенням $m x$ у початковому масиві утворюють відрізок $[l, r]$ [l, r] (де $l$ — перша поява $m x$ , $r$ — остання).

1) Розбиття на ліву та праву частину

Ми будуємо дві "півпіраміди", які з’єднуються в максимумі:

Ліва частина: елементи $a_{0} .. a_{l}$ a_0..a_l (включно з першим максимумом).
Права частина: елементи $a_{n - 1} .. a_{r}$ a_{n-1}..a_r у зворотному порядку (тобто дивимось справа наліво, включно з останнім максимумом).

У коді це масиви $b [0]$ та $b [1]$ .

Далі є допоміжна функція: $[so l v e (b, m x) \to (an s, r es)]$ [ solve(b, mx) \rightarrow (ans, res) ] яка для даного "краю" рахує дві величини:

$an s$ — повна вартість, щоб зробити цю частину сумісною з пірамідою висоти $m x$ без використання "безкоштовної вставки $c$ " як трюку;
$r es$ — те саме, але з урахуванням максимально можливого "знижкового" ефекту (місце, куди вигідно вставити безкоштовний $c$ так, щоб зекономити 1 операцію).

2) Що робить solve(a, mx)

Нехай вхідний масив $a$ — це частина, яка має стати неспадною до піка (бо ми будуємо "підйом" до максимуму).

Спочатку робимо $a$ неспадним: $[a_{i} \leftarrow max (a_{i}, a_{i - 1})]$ [ a_i \leftarrow \max(a_i, a_{i-1}) ] Вартість збільшень додається в $an s$ .
Далі йдемо справа наліво і "прибиваємо" значення так, щоб справа можна було сформувати спад $m x, m x - 1, \dots$ mx, mx-1, \dots:
Для кожного елемента беремо $[n e w_v a l = max (a_{i}, m x)]$ [ new\_val = \max(a_i, mx) ] і платимо $n e w_v a l - a_{i}$ new\_val - a_i (бо тільки збільшення дозволені). Якщо $n e w_v a l = m x$ new\_val = mx, то ми "використали" це значення для піраміди і зменшуємо потрібну висоту: $[m x \leftarrow m x - 1]$ [ mx \leftarrow mx - 1 ] Таким чином алгоритм намагається по можливості заповнити рівні $m x, m x - 1, \dots, 1$ mx, mx-1, \dots, 1 реальними елементами (з мінімальними підняттями).
Якщо після проходу залишилось $m x > 0$ mx > 0, то числа $1.. m x$ доведеться добрати вставками одиниць та підняттями (фактично це коштує суму): $[1 + 2 + \dots + m x = \frac{m x ( m x + 1 )}{2}]$ [ 1 + 2 + \dots + mx = \frac{mx(mx+1)}{2} ] Цей доданок додається до $an s$ .
"Знижка" (discount) — це максимальна кількість послідовних елементів справа, які ми піднімали (тобто де $n e w_v a l > a_{i}$ new\_val > a_i). Інтуїція така: якщо в цю ділянку вставити безкоштовний елемент $c$ , можна зекономити 1 операцію (бо один з підйомів/вставок можна замінити безкоштовною вставкою).
Також враховується випадок, коли ще залишився дефіцит рівнів $m x$ — тоді вставка $c$ може "покрити" один з потрібних рівнів.

Повертається: $[r es = an s - d i sco u n t]$ [ res = ans - discount ] тобто найкращий варіант з "однією безкоштовною вставкою" для цієї половини.

3) Як поєднати ліво і право

Є два сценарії: максимум піраміди утворюється зліва чи справа (бо вставку $c$ можна використати в різних місцях). Тому для фінальної відповіді ми комбінуємо: $[min (r es L . an s + r es R . r es, r es L . r es + r es R . an s)]$ [ \min(resL.ans + resR.res,\; resL.res + resR.ans) ] тобто в одній половині використовуємо "покращений" варіант (із знижкою), а в іншій — звичайний.

4) Випадок, коли максимум зустрічається кілька разів

Якщо $l \neq = r$ l \ne r, то у нас в початковому масиві є відрізок максимумів $[l, r]$ [l,r].

По-перше, всі елементи всередині цього відрізка, які менші за $m x$ , треба підняти до $m x$ (бо максимум має бути однаковим значенням на "плато" до обробки): $[b o n u s = \sum_{i = l}^{r} (m x - a_{i})]$ [ bonus = \sum_{i=l}^{r} (mx - a_i) ] Це просто обов’язкова доплата.

По-друге, піраміда вимагає єдиний максимум. Тому нам треба "розірвати" плато. Це робиться використанням вставки $c$ як нового піка або як елемента, який дозволяє зробити пік у потрібному місці. У коді розглядаються два підвипадки:

Якщо $r - l + 1 > 2$ r-l+1 > 2, то достатньо 1 додаткової операції (вставка 1 або підняття) для коректного формування єдиного піка, тому пробується: $[min (r es L . an s + r es R . r es, r es L . r es + r es R . an s) + 1]$ [ \min(resL.ans + resR.res,\; resL.res + resR.ans) + 1 ] разом з базовим $r es L . an s + r es R . an s$ resL.ans + resR.ans.
Якщо плато дуже коротке ( $2$ ), то треба акуратно "перевірити" обидва варіанти, прибираючи $m x$ з однієї сторони (тимчасово), перераховуючи solve, і додаючи $+ 1$ .

Фінальна відповідь друкується як: $[an s + b o n u s]$ [ ans + bonus ]

5) Окремі крайні випадки

Якщо $m x = 1$ mx=1:

при $n = 1$ n=1 треба вставити ще один елемент, щоб максимум був унікальний $\Rightarrow$ відповідь $1$ ;
інакше масив вже можна зробити пірамідальним безкоштовною вставкою $c$ (вставляємо $1$ у потрібне місце), тому відповідь $0$ .

Асимптотика

Функція solve працює за $O (k)$ для довжини масиву $k$ . В основній програмі вона викликається константну кількість разів (до кількох перерахунків у випадку короткого плато), тому загальна асимптотика: $O (n)$ Пам’ять: $O (n)$

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<class T>
using vec = vector<T>;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KoRoVa
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = -1, inf = 1000111222;

pair<ll, ll> solve (vector <int> a, int mx) { // [1, mx]
    int n = len(a);
    ll ans = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] < a[i - 1]) {
            ans += a[i - 1] - a[i];
            a[i] = a[i - 1];
        }
    }
    vector <int> b;
    int cnt = 0, discount = 0;
    for (int i = n - 1; i >= 0; i--) {
        int new_val = max(a[i], mx);
        ans += new_val - a[i];
        if (new_val == mx) {
            --mx;
        }
        if (new_val > a[i]) {
            ++cnt;
        }
        else {
            cnt = 0;
        }
        umax(discount, cnt);
    }
    assert(mx >= 0);
    ans += mx * (mx + 1ll) / 2;

    umax(discount, mx + cnt);

    ll res = ans - discount;

    LOG(ans, res, discount);

    return make_pair(ans, res);
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    vector <int> a(n);
    for (auto &i : a) cin >> i;
    int mx = *max_element(all(a));
    if (mx == 1) {
        if (n == 1) {
            cout << "1\n";
            return 0;
        }
        cout << "0\n";
        return 0;
    }
    int l = -1, r = -1;
    for (int i = 0; i < n; i++) {
        if (a[i] == mx) {
            r = i;
            if (l == -1) {
                l = i;
            }
        }
    }
    vector <int> b[2];
    for (int i = 0; i <= l; i++) {
        b[0].pb(a[i]);
    }
    for (int i = n - 1; i >= r; i--) {
        b[1].pb(a[i]);
    }
    auto resL = solve(b[0], mx);
    auto resR = solve(b[1], mx);
    if (l != r) {
        ll bonus = 0;
        for (int i = l; i <= r; i++) {
            bonus += mx - a[i];
        }
        ll ans = resL.first + resR.first;
        if (r - l + 1 > 2) {
            umin(ans, min(resL.first + resR.second, resL.second + resR.first) + 1);
        }
        else {
            for (int it = 0; it < 2; it++) {
                assert(b[it].back() == mx);
                b[it].pop_back();
                auto res1 = solve(b[0], mx);
                auto res2 = solve(b[1], mx);
                b[it].pb(mx);
                umin(ans, min(res1.first + res2.second, res1.second + res2.first) + 1);
            }
        }
        cout << ans + bonus << '\n';
        return 0;
    }
    cout << min(resL.first + resR.second, resL.second + resR.first) << '\n';
}

/*
KoRoVa!
*/

C++