题解：瑞学堂 瑞瑞的水果挑选

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

瑞学堂：瑞瑞的水果挑选

【题目描述】

瑞瑞的水果店里摆放着一排n nn个水果。每个水果只可能是苹果或桔子，从左到右依次用正整数1 , 2 , … , n 1,2,…,n1,2,…,n编号。我们用1 11代表苹果，0 00代表桔子。

连续排在一起的同一种水果称为一个“块”。瑞瑞要把这一排水果挑到若干个果篮里，具体方法是：每次都把每一个“块”中最右边的水果同时挑出，组成一个果篮。重复这一操作，直至水果用完。注意，每次挑完一个果篮后，“块”可能会发生变化。比如两个苹果“块”之间的唯一桔子被挑走后，两个苹果“块”就变成了一个“块”。

请帮瑞瑞计算每个果篮里包含的水果。

【输入】

第一行，包含一个正整数n nn，表示水果的数量。
第二行，包含n nn个空格分隔的整数，其中第i ii个数表示编号为i ii的水果的种类，1 11代表苹果，0 00代表桔子。

【输出】

输出若干行。
第i ii行表示第i ii次操作挑出的水果组成的果篮。输出时，将本次挑出的所有水果编号，按照它们所在块在当前序列中的从左到右顺序依次输出，每两个编号之间用一个空格分隔。

【输入样例】

5 1 0 1 1 0

【输出样例】

1 2 4 5 3

【核心思想】

1. 问题分析：给定长度为n nn的01 0101序列（1 11为苹果，0 00为桔子），初始将连续相同元素划分为若干"块"。每次操作从每个块的最右边取出一个元素组成果篮输出，取完后相邻同种块可能合并，重复直至所有元素取完。这是一个队列模拟 + 动态合并问题，关键在于用双端队列维护每个块，并在每轮操作后处理块的合并与压缩。

2. 算法选择：

   • 双端队列（Deque）：每个块用一个deque存储，支持从队尾弹出（取最右元素）和队首/队尾插入（合并块时保持顺序）
   • 分块模拟：将连续同种元素预分为m mm个块，每轮遍历所有块，从队尾取元素
   • 动态合并：每轮取完后，检查相邻剩余块是否种类相同，若相同则合并（将后一块的所有元素追加到前一块尾部）
   • 压缩整理：每轮结束后移除空块，压缩块编号，为下一轮做准备

3. 关键步骤：

   • 初始化分块：遍历i ii从1 11到n nn，若a i ≠ a i − 1 a_i \neq a_{i-1}ai​=ai−1​则开启新块++m，将编号i ii加入q[m]队尾
   • 循环取果篮（当m > 0 m > 0m>0）：
     • 遍历取元素：对每个块i ii（1 11到m mm）：
       • 输出q[i].back()并pop_back()
       • 若块非空，检查是否与前一个非空块last种类相同（a[q[i].front()] == a[q[last].front()]）：
         • 相同：将q[i]的所有元素从队首取出，依次push_back到q[last]，实现合并
         • 不同：last = i（记录为新的前一块）
     • 压缩块：遍历i ii从1 11到m mm，将非空块q[i]前移压缩到q[++cur]，更新m = c u r m = curm=cur
   • 输出格式：每轮操作输出一行，编号间用空格分隔

4. 时间/空间复杂度：

   • 时间复杂度：O ( n ) O(n)O(n)，每个水果编号恰好被加入和移出队列各一次，合并操作的总工作量是线性的
   • 空间复杂度：O ( n ) O(n)O(n)，所有双端队列总共存储n nn个编号

5. 队列模拟 + 动态合并的核心思想：

   • 块结构维护连续性：用双端队列将连续同种水果封装为块，保证块内元素始终有序且种类一致
   • 队尾取元素的规则映射：题目要求"每个块最右边"，直接对应deque的back()和pop_back()操作
   • 合并的惰性处理：不立即合并所有可能的相邻同种块，而是在每轮取完元素后只检查"当前块与其前一个非空块"，利用块的有序性简化合并判断
   • 压缩编号保证遍历效率：每轮结束后将非空块压缩到前部，使得每轮遍历的块数等于当前有效块数，避免稀疏数组
   • 适用于需要按固定规则从多个分组中轮流取元素，且分组间存在动态合并/分裂的场景

【算法标签】

#队列

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=200005;// 定义数组最大容量为200005deque<int>q[N];// q[i]为双端队列，存储第i个"块"中所有水果的编号（保持从左到右顺序）intn,a[N];// n为水果数量，a[i]表示第i个水果的种类（1为苹果，0为桔子）intmain(){cin>>n;// 读入水果数量nfor(inti=1;i<=n;i++)// 读入每个水果的种类cin>>a[i];intm=0;// m记录当前"块"的数量// 第一步：将连续的同种水果划分为"块"，每个块用一个双端队列存储for(inti=1;i<=n;i++){// 如果当前水果是第一个，或者与上一个水果种类不同，则开启一个新块if(i==1||a[i]!=a[i-1])++m;// 块数量加1q[m].push_back(i);// 将当前水果编号加入当前块的队列尾部}// 第二步：循环挑出果篮，直到所有水果都被挑完while(m>0)// 当还有块存在时继续{intlast=0;// last记录上一个未被合并的块的编号，用于判断相邻块是否需要合并// 遍历每个块，挑出每个块最右边的水果（队尾）for(inti=1;i<=m;i++){// 输出当前块最右边水果的编号（每次操作都从每个块的最右边挑）cout<<q[i].back()<<" ";q[i].pop_back();// 将该水果从块中移除（挑出）// 如果该块还有剩余水果，检查是否需要与上一个块合并if(!q[i].empty()){// 如果上一个块存在，且当前块队首水果与上一个块队首水果种类相同// 说明中间被挑走的水果使得两个同种块相邻，需要合并if(last>0&&a[q[i].front()]==a[q[last].front()]){// 将当前块的所有剩余水果合并到上一个块中（保持顺序）while(!q[i].empty()){q[last].push_back(q[i].front());// 从当前块头部取出，加入上一个块尾部q[i].pop_front();// 从当前块头部移除}}else{last=i;// 当前块无法合并，记录为新的"上一个块"}}}cout<<endl;// 输出完当前果篮后换行// 第三步：整理块，移除空块，压缩队列编号intcur=0;// cur记录整理后的有效块数量for(inti=1;i<=m;i++){if(!q[i].empty())// 如果第i个块还有剩余水果q[++cur]=q[i];// 将其移动到前面，压缩编号（双端队列可以直接赋值）}m=cur;// 更新块的数量}return0;}

【运行结果】

5 1 0 1 1 0 1 2 4 5 3