题解：糖果美味度最大化问题

题目分析

本题要求在不能吃连续糖果的约束下，对于每个 j（1 ≤ j ≤ ⌈N/2⌉），求出吃 j 块糖时的最大美味度和。核心是在“选或不选”的约束下，高效处理多组最优解的求解。

方法思路：反悔贪心 + 双向链表

我们可以通过反悔贪心结合双向链表的方式解决：

1. 局部最大值筛选：初始时找到所有“局部最大值”（即该糖果的美味度大于等于左右相邻糖果，若相邻不存在则视为无穷大），这些是候选的最优选择。
2. 贪心选择与反悔机制：每次选当前最大的局部最大值，然后构造“反悔选项”（用左右邻居的和减去当前值，模拟“撤销当前选择并选左右”的操作），并维护双向链表来更新相邻关系。
3. 前缀和求解多组答案：将所有选择按价值降序排列后，前缀和即为吃 j 块糖时的最大和。

解决代码

#include <bits/stdc++.h>
typedef long long ll;
const int N = 200010;

int n;
ll a[N], prv[N], nxt[N], ans[N / 2];
bool vis[N];
std::priority_queue<std::pair<ll, int>> pq; // 大根堆，存储(美味度, 位置)

// 检查节点i是否是局部最大值
void check(int i) {
    if (vis[i]) return;
    if (prv[i] && a[i] < a[prv[i]]) return;
    if (nxt[i] <= n && a[i] <= a[nxt[i]]) return;
    vis[i] = true;
    pq.emplace(a[i], i);
}

// 从链表中删除节点i
void erase(int i) {
    if (i < 1 || i > n) return;
    int l = prv[i], r = nxt[i];
    nxt[l] = r;
    prv[r] = l;
}

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

    std::cin >> n;
    for (int i = 1; i <= n; ++i) std::cin >> a[i];

    // 初始化双向链表
    for (int i = 0; i <= n; ++i) {
        nxt[i] = i + 1;
        prv[i + 1] = i;
    }
    vis[0] = vis[n + 1] = true; // 边界标记为已访问

    // 初始局部最大值入堆
    for (int i = 1; i <= n; ++i) check(i);

    int cnt = 0;
    while (!pq.empty() && cnt < (n + 1) / 2) {
        auto [val, i] = pq.top();
        pq.pop();
        if (!vis[i]) continue; // 已被删除，跳过

        ans[++cnt] = val;
        ll new_val = a[prv[i]] + a[nxt[i]] - a[i];
        a[i] = new_val;

        bool is_boundary = (prv[i] == 0) || (nxt[i] == n + 1);
        erase(prv[i]);
        erase(nxt[i]);

        (is_boundary ? erase : check)(i);
        check(prv[i]);
        check(nxt[i]);
    }

    // 计算前缀和（因为ans已按降序排列）
    for (int i = 1; i <= cnt; ++i) {
        ans[i] += ans[i - 1];
        std::cout << ans[i] << '\n';
    }

    return 0;
}

代码解释

1. 数据结构与初始化：

   • 用数组 prv 和 nxt 维护双向链表，记录每个位置的前驱和后继。
   • 大根堆 pq 用于快速获取当前最大的局部最大值。

2. 局部最大值检查 check 函数： 判断位置 i 是否是局部最大值（即大于等于左右邻居，无邻居则视为满足），若是则标记为vis[i]=true并加入堆中。

3. 链表删除 erase 函数： 从双向链表中删除位置 i，并更新其前驱和后继的指针。

4. 主逻辑：

   • 初始将所有局部最大值入堆。
   • 每次从堆中取最大元素，记录其价值，然后构造反悔选项（a[i] = 左+右-当前）。
   • 删除其左右邻居（因为不能选连续糖果），并重新检查当前位置和新的邻居是否成为局部最大值。

5. 结果输出： 由于每次选择的价值是降序的，前缀和即为吃 j 块糖时的最大和，直接输出前缀和数组即可。

该方法的时间复杂度为 ( O(N \log N) )，能够高效处理 ( N \leq 2 \times 10^5 ) 的数据规模。