题解：P14374 [JOISC 2018] 糖果 / Candies

sccc_ · 2026-07-23 19:11:35 · 题解

Solution

对于这道题，考虑反悔贪心。

为什么是反悔贪心？

普通贪心每次选当前单颗糖的最大美味值 x，但可能存在这颗糖的邻居糖 L + R > x，此时选左右两颗比选中间更优，需要反悔。

反悔策略

选出 x 后，向堆中插入一个新节点，权值为 L + R - x。若之后该节点被选中，其贡献与之前选中的 x 叠加后为 x + (L + R - x) = L + R，等效于撤销 x 并添加 L 和 R，可以刚好使得选中数量加一。

用链表维护当前节点左右两边、优先队列维护最大值即可。

Code

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2e5 + 5;

int n, tot, a[N], lt[N], rt[N];
bool vis[N];

struct Node {
    int val, idx;
    bool operator < (const Node &nxt) const {
        return val < nxt.val;
    }
};
priority_queue<Node> q;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    a[0] = a[n + 1] = -1e18;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        lt[i] = i - 1;
        rt[i] = i + 1;
        q.push({a[i], i});
    }
    int ans = 0;
    for (int i = 1; i <= ((n + 1) >> 1); i++) {
        while (!q.empty() && vis[q.top().idx])
            q.pop();
        auto [val, idx] = q.top();
        q.pop();
        ans += a[idx];
        cout << ans << '\n';
        a[idx] = a[lt[idx]] + a[rt[idx]] - a[idx];
        int l = lt[idx];
        rt[lt[l]] = rt[l];
        lt[rt[l]] = lt[l];
        vis[l] = 1;
        int r = rt[idx];
        rt[lt[r]] = rt[r];
        lt[rt[r]] = lt[r];
        vis[r] = 1;
        q.push({a[idx], idx});
    }
    return 0;
}