2021 小熊的果篮 · 方案二链表加有序集合

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 5/5 · 共 1761 字

摘掉块头后只影响前后邻居，用 set 维护块头

2021
链表

正文

// CSP-J 2021 复赛 T4 · 小熊的果篮（方案二 · 满分）
// 原题：https://oj.yecheng.tv/p/CSPJ2021D
//
// 方案二 · 双向链表 + 有序集合维护块头
// 每轮重扫太浪费了。真正会变的只有「被挑走的块头的前驱和后继」：
// 把块头 i 摘掉后，它的前驱 p 和后继 q 就挨在一起了 ——
//   · 若 p 不存在，或者 a[p] != a[q]，那 q 就成了新块的块头；
//   · 否则 q 并进了 p 所在的块，不再是一个块头。
// 于是用一个双向链表支持 O(1) 摘除，用一个 set 存当前所有块头。
// 每轮：先把 set 里的块头全部输出，然后统一摘除、再统一更新块头。
// 注意两个坑：
//   1. 必须先把这一轮要摘的全标记成 gone，再判断 q —— 否则会把本轮也要摘掉的点
//      当成下一轮的块头加进 set；
//   2. 摘除和块头更新要分成两趟循环，否则前后驱还没改完，判断就错了。
// 复杂度 O(n log n)。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
int a[MAXN], pre[MAXN], nxt[MAXN];
bool gone[MAXN];

int main() {
    freopen("fruit.in", "r", stdin);
    freopen("fruit.out", "w", stdout);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        pre[i] = i - 1;
        nxt[i] = i + 1;
    }
    nxt[n] = n + 1;

    set<int> heads;
    for (int i = 1; i <= n; i++) {
        if (i == 1 || a[i] != a[i - 1]) heads.insert(i);
    }

    while (!heads.empty()) {
        vector<int> cur(heads.begin(), heads.end());
        heads.clear();
        for (size_t k = 0; k < cur.size(); k++) {
            cout << cur[k] << (k + 1 == cur.size() ? '\n' : ' ');
        }

        for (int i : cur) gone[i] = true;
        for (int i : cur) {                       // 第一趟：把 i 从链表里摘掉
            int p = pre[i];
            int q = nxt[i];
            if (p >= 1) nxt[p] = q;
            if (q <= n) pre[q] = p;
        }
        for (int i : cur) {                       // 第二趟：决定 q 还是不是块头
            int p = pre[i];
            int q = nxt[i];
            if (q > n || gone[q]) continue;
            if (p < 1 || a[p] != a[q]) heads.insert(q);
            else heads.erase(q);
        }
    }
    return 0;
}

2021 小熊的果篮 · 方案二 链表加有序集合

正文

CSP-J 标程 · 复赛真题的其它内容

2021 小熊的果篮 · 方案二链表加有序集合