K 低谷

知识点：双向链表反悔自动机

写在前面

本来这题的原题数据是 的，没有这个 Hard 版本，Ease 版本的正解是一个时间复杂度为 的 DP。但是我在验题时没有想到 DP，反而想到了时间复杂度更优（指 ）的反悔贪心的做法，于是便有了这题的 Hard 版本

思路

显然我们可以预处理出来将每个位置变成低谷所需代价

由于低谷的特性，显然我们选择的两个低谷不能相邻，那么题目就变成了：在序列中选择不相邻的若干个位置 ，使得 ，求最大的

看到相邻位置不能选择，考虑反悔贪心中的双向链表反悔自动机，可以参考例题：P1484 种树 - 洛谷

1. 当选择一个点 的时候，由于相邻节点无法选择，我们选择删除左右节点

2. 如果点 不是左端点和右端点，我们需要将 重新赋值成 ，并塞入堆中，实现反悔贪心

由于每个点的进入必定伴随着其他点的删除，因此堆中最多进入 个点，时间复杂度

AC 代码

#include <bits/stdc++.h>
using std::cin, std::cout, std::vector, std::array;
using ll = long long;
using PII = std::pair<int, int>;
using PLI = std::pair<ll, int>;

void solve()
{
    int n,k; cin>>n>>k;
    vector<ll> aa(n), cost(n, 1e12);
    for(auto &i:aa) cin>>i;
    for(int i=1; i<n-1; ++i)
        cost[i] = std::max(0LL, aa[i]-std::min(aa[i-1], aa[i+1])+1);
    
    vector<PII> it(n);
    for(int i=1; i<n-1; ++i) it[i] = {i-1, i+1};
    it[0] = {0, 1}, it[n-1] = {n-2, n-1};

    std::priority_queue<PLI, vector<PLI>, std::greater<>> pq;
    for(int i=1; i<n-1; ++i) pq.emplace(cost[i], i);

    vector<short> deled(n);
    
    auto del = [&](int id) {
        auto [L, R] = it[id];
        deled[id] = 1;
        it[L].second = R, it[R].first = L;
    };

    int res = 0;
    ll sum = 0;
    while(!pq.empty()) {
        auto [uCost, u] = pq.top(); pq.pop();
        if(deled[u]) continue;
        sum += uCost;
        if(sum> k) break;
        ++res;

        auto [L, R] = it[u];
        if(L != 0) del(L);
        if(R != n-1) del(R);
        if(L != 0 && R != n-1) {
            cost[u] = cost[L]+cost[R]-uCost;
            pq.emplace(cost[u], u);
        } else {
            del(u);
        }
    }
    cout<<res<<"\n";
}

int32_t main()
{
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    // std::cin>>T;
    while(T--) solve();
    return 0;
}