[CSP-J 2021-T4] 小熊的果篮摘要本题为 CSP-J 2021 T4要求模拟「每次从每个连续水果块的最左边取一个水果」的过程直到取完。核心在于用双向链表实现 O(1) 删除同时只维护每轮的「块首」列表避免全量遍历带来的 O(n²) 复杂度。文章从暴力瓶颈出发逐步推导新块首的判定条件给出了完整的 C 实现并总结了哨兵边界、IO 优化、块合并逻辑等常见易错点。题目描述小熊的水果店里摆放着一排n nn个水果。每个水果只可能是苹果或桔子从左到右依次用正整数1 , 2 , … , n 1, 2, \ldots, n1,2,…,n编号。连续排在一起的同一种水果称为一个“块”。小熊要把这一排水果挑到若干个果篮里具体方法是每次都把每一个“块”中最左边的水果同时挑出组成一个果篮。重复这一操作直至水果用完。注意每次挑完一个果篮后“块”可能会发生变化。比如两个苹果“块”之间的唯一桔子被挑走后两个苹果“块”就变成了一个“块”。请帮小熊计算每个果篮里包含的水果。输入格式第一行包含一个正整数n nn表示水果的数量。第二行包含n nn个空格分隔的整数其中第i ii个数表示编号为i ii的水果的种类1 11代表苹果0 00代表桔子。输出格式输出若干行。第i ii行表示第i ii次挑出的水果组成的果篮。从小到大排序输出该果篮中所有水果的编号每两个编号之间用一个空格分隔。输入输出样例 #1输入 #112 1 1 0 0 1 1 1 0 1 1 0 0输出 #11 3 5 8 9 11 2 4 6 12 7 10输入输出样例 #2输入 #220 1 1 1 1 0 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0输出 #21 5 8 11 13 14 15 17 2 6 9 12 16 18 3 7 10 19 4 20输入输出样例 #3输入 #3见附件中的 fruit/fruit3.in。输出 #3见附件中的 fruit/fruit3.ans。说明/提示【样例解释 #1】这是第一组数据的样例说明。所有水果一开始的情况是[ 1 , 1 , 0 , 0 , 1 , 1 , 1 , 0 , 1 , 1 , 0 , 0 ] [1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0][1,1,0,0,1,1,1,0,1,1,0,0]一共有6 66个块。在第一次挑水果组成果篮的过程中编号为1 , 3 , 5 , 8 , 9 , 11 1, 3, 5, 8, 9, 111,3,5,8,9,11的水果被挑了出来。之后剩下的水果是[ 1 , 0 , 1 , 1 , 1 , 0 ] [1, 0, 1, 1, 1, 0][1,0,1,1,1,0]一共4 44个块。在第二次挑水果组成果篮的过程中编号为2 , 4 , 6 , 12 2, 4, 6, 122,4,6,12的水果被挑了出来。之后剩下的水果是[ 1 , 1 ] [1, 1][1,1]只有1 11个块。在第三次挑水果组成果篮的过程中编号为7 77的水果被挑了出来。最后剩下的水果是[ 1 ] [1][1]只有1 11个块。在第四次挑水果组成果篮的过程中编号为10 1010的水果被挑了出来。【数据范围】对于10 % 10 \%10%的数据n ≤ 5 n \le 5n≤5。对于30 % 30 \%30%的数据n ≤ 1000 n \le 1000n≤1000。对于70 % 70 \%70%的数据n ≤ 50000 n \le 50000n≤50000。对于100 % 100 \%100%的数据1 ≤ n ≤ 2 × 10 5 1 \le n \le 2 \times {10}^51≤n≤2×105。【提示】由于数据规模较大建议 C/C 选手使用scanf和printf语句输入、输出。思路要点给你一排由0 00和1 11编码表示的水果序列1 11代表苹果0 00代表桔子你需要把连续相同的水果看作一个“块”例如连续的苹果是一个块连续的桔子也是一个块。每轮操作按从左到右的顺序从每个块的最左边拿走一个水果组成果篮并按编号输出。拿走水果后原来的序列会重新拼接。如果拼接后两个原本不在一起的同类块碰头了它们就会合并成一个新的块。重复这个过程直到所有水果被拿完。关键思路暴力思路的瓶颈如果我们直接用数组或者vector模拟“删除元素”每次删除后把后面的元素整体向前移动时间复杂度是O ( n 2 ) O(n^2)O(n2)。对于数据范围n ≤ 2 × 10 5 n \le 2 \times 10^5n≤2×105n 2 n^2n2的计算量高达4 × 10 10 4 \times 10^{10}4×1010只能拿到30 3030到70 7070分必然超时。优化一O ( 1 ) O(1)O(1)删除元素——双向链表既然数组移动太慢我们自然想到用双向链表。通过l[i]记录编号为i ii的水果左边的水果编号r[i]记录右边的水果编号。删除一个节点y yy只需要修改它左右邻居的指向r [ l [ y ] ] r [ y ] , l [ r [ y ] ] l [ y ] r[l[y]] r[y], \quad l[r[y]] l[y]r[l[y]]r[y],l[r[y]]l[y]。这样删除一个节点的复杂度就能降到O ( 1 ) O(1)O(1)。优化二跳过无用遍历 —— 只维护“块首”即使用了链表如果每一轮都从头到尾扫一遍链表去找“块首”在最坏情况下比如所有水果都是同一种仍然需要遍历O ( n ) O(n)O(n)次总复杂度还是O ( n 2 ) O(n^2)O(n2)。但其实我们不需要遍历每个水果只需要维护当前所有“块首水果的编号”。假设当前轮次的块首集合保存在数组v中我们依次打印并删除v中的这些节点。重点在于删除节点y yy后它的右邻居z zz会不会成为下一轮的“新块首”“新块首” 判定逻辑推导设删除的块首节点为y yy其左邻居为x xx右邻居为z zz即状态变化为[ x → y → z ] ⟹ [ x → z ] [x \to y \to z] \Longrightarrow [x \to z][x→y→z]⟹[x→z]z zz如果要成为新块首它原本必须和y yy属于同一个块即a [ z ] a [ y ] a[z] a[y]a[z]a[y]。如果a [ z ] ≠ a [ y ] a[z] \ne a[y]a[z]a[y]说明z zz原本就是另一个块的开头它已经在当前的v数组里被处理或等待处理了不需要重复加入。z zz不能和它新的左邻居x xx同类即a [ z ] ≠ a [ x ] a[z] \ne a[x]a[z]a[x]。如果a [ z ] a [ x ] a[z] a[x]a[z]a[x]说明y yy被删掉后z zz和左边的x xx合并成了一个大块z zz变成了这个大块的内部后继元素而不是块首。例如[1, 1, 0, 1, 1]这组序列第一轮取出编号为1 3 4的水果后编号2会成为新块首但编号5由于和编号2为同一水果因此并不构成下一轮的块首。因此只有同时满足上述两个条件a [ z ] a [ y ] a[z] a[y]a[z]a[y]且a [ z ] ≠ a [ x ] a[z] \ne a[x]a[z]a[x]z zz才会成为下一轮产生的新块首我们将下轮新块首元素依次放入另一个更新数组t中每轮结束后用t替换v。解题步骤定义数组与边界哨兵定义a数组存储水果类型双向链表数组l左邻居、r右邻居以及动态数组v存储当前轮次所有块首的水果编号。设置边界哨兵a[0] a[n 1] -1防止程序在判断边界相邻元素时发生越界。读入数据与初始化链表循环读入每个水果种类a[i]同时初始化双向链表指针l[i] i - 1r[i] i 1。识别初始块首如果a[i] ! a[i - 1]说明i处的元素与前一个水果种类不同是一个“新块”的开头将其下标存入块首数组v.push_back(i)。核心模拟循环while(v.size())只要v不为空说明序列中还有水果未被挑完就重复执行以下步骤创建下一轮的临时块首数组t定义vectorint t专门用来收集本轮删除节点后产生的下一轮新块首编号。遍历当前轮次的所有块首for循环输出当前块首执行printf(%d , v[i]);将当前块最左边的水果编号存入本轮果篮并打印。提取三元组节点[ x → y → z ] [x \to y \to z][x→y→z]y v [ i ] y v[i]yv[i]即将被删除的当前块首x l [ y ] x l[y]xl[y]y yy在链表中的左邻居z r [ y ] z r[y]zr[y]y yy在链表中的右邻居。链表O ( 1 ) O(1)O(1)删除节点y yy执行r[x] z; l[z] x;更新左右邻居的指向将y yy从链表中断开使结构变为[ x → z ] [x \to z][x→z]。判定右邻居z zz是否成为下一轮的新块首条件判断if (a[z] a[y] a[z] ! a[x])逻辑说明a[z] a[y]z zz与被删掉的y yy水果种类相同说明z zz是y yy所在块中紧挨着的下一个元素有资格“顺位继承”块首位置a[z] ! a[x]z zz与新的左邻居x xx水果种类不同说明z zz没有和左边的块合并仍然是一个独立块的开头。若同时满足上述两点将z zz加入下一轮的新块首列表t.push_back(z);。轮次切换与换行本轮所有块首处理完毕后打印换行printf(\n);代表一个果篮组装完成。执行v t;用最新收集的块首数组t覆盖v进入下一轮处理。本题易错点坑一边界越界风险哨兵机制要点提醒在检查a [ x ] a[x]a[x]或a [ z ] a[z]a[z]时如果x 0 x0x0删除了序列第一个元素或者z n 1 zn1zn1删除了序列最后一个元素直接访问a [ 0 ] a[0]a[0]或a [ n 1 ] a[n1]a[n1]可能会读取到未知废值。因此可以在开局设置a [ 0 ] a [ n 1 ] − 1 a[0] a[n1] -1a[0]a[n1]−1利用哨兵隔离边界这样既不会越界也不会和任何正常的类型0 00或1 11混淆。坑二IO 性能问题要点提醒本题数据量n 2 × 10 5 n 2 \times 10^5n2×105输出行数较多一定要使用scanf/printf或者开启cin/cout解绑cin.tie(0)避免因输入输出耗费过多时间。坑三块合并的逻辑漏洞要点提醒如果不写条件a [ z ] ≠ a [ x ] a[z] \ne a[x]a[z]a[x]当两个苹果块中间唯一的一个桔子被拿走后右边的苹果块首节点仍然会被加入t中导致同一个苹果块被记了两次不同的块首。参考代码#includebits/stdc.h#definemaxn200005usingnamespacestd;intn,a[maxn],r[maxn],l[maxn];vectorintv;// 存当前轮次每块水果的开头编号intmain(){scanf(%d,n);a[0]a[n1]-1;// 设置首末哨兵特殊值防止判断相邻元素时数组越界for(inti1;in;i){scanf(%d,a[i]);r[i]i1,l[i]i-1;// 初始化双向链表左右指针if(a[i]!a[i-1]){// 如果与前一个水果类型不同 - 发现了新块v.push_back(i);// 记录新块的起始下标}}while(v.size()){// 只要还有未处理的块vectorintt;// 存下一轮更新后的新块首地址for(inti0;iv.size();i){// 遍历当前所有的块首printf(%d ,v[i]);// 依次取出并输出块首编号// 取出当前节点 y以及它的左邻居 x 和右邻居 zintxl[v[i]],yv[i],zr[v[i]];// 从双向链表中删除节点 y[x - y - z] 变为 [x - z]r[x]z,l[z]x;// 判断右邻居 z 是否成为新的块首// 条件1a[z] a[y] (z 与被删掉的 y 是同种水果说明 z 是 y 所在块剩下的部分)// 条件2a[z] ! a[x] (z 与新左邻居 x 不同种说明没有与 x 所在的块合并)if(a[z]a[y]a[z]!a[x]){t.push_back(z);}}printf(\n);// 每一轮水果拿完换行vt;// 将更新后的块首列表赋给 v进入下一轮}return0;}