JOISC 2018 糖果 题解

题目描述

有 $N$ 块糖排成一排，每块糖有一个美味度 $A_i$。JOI 酱想吃一些糖，但不能吃相邻的糖。对于每个 $j$ $(1 \le j \le \lceil \frac{N}{2} \rceil)$，需要求出吃 $j$ 块糖时能获得的最大美味度之和。

算法思路

本题使用反悔贪心算法解决。核心思想是：

1. 维护一个双向链表表示糖果的相邻关系
2. 使用队列存储当前可选的局部最大值
3. 每次选择价值最大的糖果，并通过价值更新实现"反悔"机制
4. 将每次选择的价值排序后求前缀和得到最终答案

完整代码

#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::queue<int> q;

// 检查节点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;
    q.push(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);

    // 主循环：进行最多 ⌈n/2⌉ 次选择
    for (int rep = 1; rep <= (n + 1) / 2; ++rep) {
        // 取出当前最优的糖果
        int i = q.front();
        q.pop();
        vis[i] = false;
        
        // 记录这次选择的价值
        ans[rep] = a[i];
        
        // 创建反悔选项：新价值 = 左邻居 + 右邻居 - 当前值
        a[i] = a[prv[i]] + a[nxt[i]] - a[i];
        
        // 检查当前节点是否是边界节点
        bool fl = (prv[i] == 0) || (nxt[i] == n + 1);
        
        // 删除相邻节点（因为不能选择相邻糖果）
        erase(prv[i]);
        erase(nxt[i]);
        
        // 如果是边界节点则删除当前节点，否则重新检查
        (fl ? erase : check)(i);
        
        // 检查新的邻居节点
        check(prv[i]);
        check(nxt[i]);
    }

    // 将选择的价值按降序排序
    std::sort(ans + 1, ans + (n + 1) / 2 + 1, std::greater<ll>());

    // 输出前缀和作为答案
    for (int i = 1; i <= (n + 1) / 2; ++i) {
        ans[i] += ans[i - 1];
        std::cout << ans[i] << '\n';
    }

    return 0;
}

算法详解

1. 数据结构

• a[i]: 存储第i个糖果的美味度
• prv[i], nxt[i]: 双向链表，维护糖果的相邻关系
• vis[i]: 标记节点是否在队列中
• ans[i]: 存储第i次选择的价值

2. 关键函数

check(i) 函数：

• 检查节点i是否是局部最大值
• 只有比左右邻居都严格大的节点才会加入队列
• 这确保了每次选择都是当前最优的

erase(i) 函数：

• 从双向链表中删除节点i
• 更新相邻节点的指针

3. 反悔机制

核心代码：

a[i] = a[prv[i]] + a[nxt[i]] - a[i];

这行代码实现了反悔：

• 如果我们之前选择了左右邻居而不是i，那么价值差就是 (a[左] + a[右]) - a[i]
• 如果这个新价值为正，说明选择左右邻居比选择i更优
• 这样算法就有了修正之前选择的能力

4. 时间复杂度

• O(N)：每个节点最多被处理一次
• O(N log N)：最终排序操作
• 总复杂度：O(N log N)，可以处理N = 2×10^5的数据规模

示例运行

输入：

5
3
5
1
7
6

输出：

7
12
10

解释：

• 选1个糖果：选择第4个（美味度7）
• 选2个糖果：选择第2个和第4个（美味度5+7=12）
• 选3个糖果：选择第1、3、5个（美味度3+1+6=10）

总结

这个反悔贪心算法巧妙地解决了带相邻约束的最大子集和问题。通过维护双向链表和局部最大值队列，结合价值更新的反悔机制，算法能够在O(N log N)时间内求出所有j的答案，效率很高且代码简洁。