你好！我是你的OI教练。

这道题（CSP-J 2021 T4 小熊的果篮）是一道非常经典的链表模拟题。虽然题目描述是关于挑选水果，但核心难点在于如何高效地处理“块”的合并和删除。如果直接使用数组或 vector 进行 $O(N^2)$ 的暴力模拟，对于 $N=2 \times 10^5$ 的数据范围肯定会超时。

我们需要一个接近 $O(N)$ 的解法。

解题思路

1. 数据结构选择： 我们需要频繁地进行以下操作：

   • 遍历当前的“块”。
   • 删除空的“块”。
   • 合并相邻且类型相同的“块”。 这正是**链表（Linked List）**最擅长的领域。我们可以使用 C++ STL 中的 std::list。

2. “块”的表示： 我们将连续的同种水果看作一个Block（块）。 每个 Block 包含：

   • type: 水果种类（0 或 1）。
   • q: 一个队列（或链表），存储该块中所有水果的原始编号。

3. 模拟流程：

   • 初始化：读取输入，将连续相同的数字归为一个 Block，放入主链表 blocks 中。
   • 挑选循环（直到水果取完）：
     1. 挑选阶段：遍历链表中的每一个 Block，输出其队列头部的编号（最左边的水果），并将该编号弹出。
     2. 清理阶段：遍历链表，删除已经变为空（队列为空）的 Block。
     3. 合并阶段：再次遍历链表，检查相邻的两个 Block。如果它们的 type 相同（说明中间隔开它们的异类块被删除了），则使用 splice 操作将后一个块的水果合并到前一个块中，并删除后一个块。

4. 复杂度分析： 虽然看起来有三重循环（外层 while，内层遍历、清理、合并），但实际上：

   • 每个水果只会被输出并弹出一次。
   • 每个 Block 初始创建一次，最多被合并或删除一次。
   • 内层的遍历次数总和与水果总数成正比（因为每次遍历都会至少取走一个水果）。 因此，总的时间复杂度是 $O(N)$，可以完美通过。

标准 AC 代码 (C++)

#include <cstdio>
#include <list>
#include <iterator>

using namespace std;

// 定义块结构体
struct Block {
    int type;           // 水果种类：0 或 1
    list<int> indices;  // 存储该块中水果的编号，使用 list 支持 O(1) 合并
};

int main() {
    int n;
    // 使用 scanf 加快读入速度
    if (scanf("%d", &n) != 1) return 0;

    list<Block> blocks;

    // --- 1. 读入数据并构建初始块 ---
    for (int i = 1; i <= n; ++i) {
        int type;
        scanf("%d", &type);
        
        // 如果链表为空，或者当前水果类型与链表最后一个块的类型不同
        // 则创建一个新块
        if (blocks.empty() || blocks.back().type != type) {
            blocks.emplace_back();      // 原地构造新块
            blocks.back().type = type;
        }
        // 将当前水果编号加入最后一个块的队列中
        blocks.back().indices.push_back(i);
    }

    int remaining = n; // 剩余水果数量

    // --- 2. 模拟挑选过程 ---
    while (remaining > 0) {
        // [阶段 A]：从每个块中挑选一个水果
        for (auto it = blocks.begin(); it != blocks.end(); ++it) {
            printf("%d ", it->indices.front()); // 输出队头
            it->indices.pop_front();            // 弹出队头
            remaining--;
        }
        printf("\n"); // 一轮结束换行

        // [阶段 B]：清理空块
        // 遍历链表，删除已经没有水果的块
        for (auto it = blocks.begin(); it != blocks.end(); ) {
            if (it->indices.empty()) {
                it = blocks.erase(it); // erase 返回下一个有效的迭代器
            } else {
                ++it;
            }
        }

        // [阶段 C]：合并相邻同类型块
        // 因为空块被删除，原来不相邻的块可能变得相邻
        if (!blocks.empty()) {
            auto it = blocks.begin();
            auto next_it = next(it); // 获取下一个迭代器
            
            while (next_it != blocks.end()) {
                // 如果当前块和下一个块类型相同
                if (it->type == next_it->type) {
                    // 使用 splice 将 next_it 的所有元素以 O(1) 移动到 it 的末尾
                    it->indices.splice(it->indices.end(), next_it->indices);
                    
                    // 删除被合并的块
                    blocks.erase(next_it);
                    
                    // 更新 next_it，继续检查 it 能否和新的邻居合并
                    // 注意：这里不用 ++it，因为合并后的 it 可能还需要和后面合并
                    next_it = next(it); 
                } else {
                    // 类型不同，移动到下一对
                    it = next_it;
                    next_it++;
                }
            }
        }
    }

    return 0;
}

代码关键点解释

1. list<int> indices：在 Block 内部我们也使用了 list 而不是 vector 或 queue。这是因为 std::list 提供了一个非常强大的函数 splice，它可以 $O(1)$ 地将一个链表的所有元素“接”到另一个链表上。这在合并块时非常关键。
2. 合并逻辑：it->indices.splice(it->indices.end(), next_it->indices); 这行代码直接把 next_it 里的所有编号接到了 it 的后面，不需要一个一个元素拷贝，极大地提高了效率。
3. 迭代器操作：在遍历链表进行删除（erase）操作时，要注意迭代器的失效问题。it = blocks.erase(it) 是标准的写法，它会删除当前元素并让 it 指向下一个元素。

加油！掌握链表和模拟的结合是解决这类问题的关键。