Problem J: 伊菲的数据结构

📝 题目描述

🔑 算法模块

💡 思路分析

初始时每个间隔长度为 \(1\)，我们需要找到一个最高的间隔，令其长度变成 \(2\)。

不难发现每个间隔高度为其左边最高的隔板和其右边最高的隔板中较小的一个的高度。

预处理一个最大后缀和即可。

🖥️ 代码实现

#include <bits/stdc++.h>
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, mx = 0, mxx = 0;
    long long ans = 0;
    std::cin >> n;
    std::vector<int> a(n), b(n), c(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    b[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        b[i] = std::max(b[i + 1], a[i]);
    }
    for (int i = 0; i < n; i++) {
        int x = std::min(mx, b[i]);
        ans += x;
        mxx = std::max(mxx, x);
        mx = std::max(mx, a[i]);
    }
    ans += mxx;
    std::cout << ans << "\n";
    return 0;
}

⏱️ 复杂度分析

📚 拓展