本文分享的必刷题目是从蓝桥云课、洛谷、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【核心思想】问题分析给定长度为n nn的01 0101序列1 11为苹果0 00为桔子初始将连续相同元素划分为若干块。每次操作从每个块的最右边取出一个元素组成果篮输出取完后相邻同种块可能合并重复直至所有元素取完。这是一个队列模拟 动态合并问题关键在于用双端队列维护每个块并在每轮操作后处理块的合并与压缩。算法选择双端队列Deque每个块用一个deque存储支持从队尾弹出取最右元素和队首/队尾插入合并块时保持顺序分块模拟将连续同种元素预分为m mm个块每轮遍历所有块从队尾取元素动态合并每轮取完后检查相邻剩余块是否种类相同若相同则合并将后一块的所有元素追加到前一块尾部压缩整理每轮结束后移除空块压缩块编号为下一轮做准备关键步骤初始化分块遍历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 0m0遍历取元素对每个块i ii1 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 curmcur输出格式每轮操作输出一行编号间用空格分隔时间/空间复杂度时间复杂度O ( n ) O(n)O(n)每个水果编号恰好被加入和移出队列各一次合并操作的总工作量是线性的空间复杂度O ( n ) O(n)O(n)所有双端队列总共存储n nn个编号队列模拟 动态合并的核心思想块结构维护连续性用双端队列将连续同种水果封装为块保证块内元素始终有序且种类一致队尾取元素的规则映射题目要求每个块最右边直接对应deque的back()和pop_back()操作合并的惰性处理不立即合并所有可能的相邻同种块而是在每轮取完元素后只检查当前块与其前一个非空块利用块的有序性简化合并判断压缩编号保证遍历效率每轮结束后将非空块压缩到前部使得每轮遍历的块数等于当前有效块数避免稀疏数组适用于需要按固定规则从多个分组中轮流取元素且分组间存在动态合并/分裂的场景【算法标签】#队列【代码详解】#includebits/stdc.husingnamespacestd;constintN200005;// 定义数组最大容量为200005dequeintq[N];// q[i]为双端队列存储第i个块中所有水果的编号保持从左到右顺序intn,a[N];// n为水果数量a[i]表示第i个水果的种类1为苹果0为桔子intmain(){cinn;// 读入水果数量nfor(inti1;in;i)// 读入每个水果的种类cina[i];intm0;// m记录当前块的数量// 第一步将连续的同种水果划分为块每个块用一个双端队列存储for(inti1;in;i){// 如果当前水果是第一个或者与上一个水果种类不同则开启一个新块if(i1||a[i]!a[i-1])m;// 块数量加1q[m].push_back(i);// 将当前水果编号加入当前块的队列尾部}// 第二步循环挑出果篮直到所有水果都被挑完while(m0)// 当还有块存在时继续{intlast0;// last记录上一个未被合并的块的编号用于判断相邻块是否需要合并// 遍历每个块挑出每个块最右边的水果队尾for(inti1;im;i){// 输出当前块最右边水果的编号每次操作都从每个块的最右边挑coutq[i].back() ;q[i].pop_back();// 将该水果从块中移除挑出// 如果该块还有剩余水果检查是否需要与上一个块合并if(!q[i].empty()){// 如果上一个块存在且当前块队首水果与上一个块队首水果种类相同// 说明中间被挑走的水果使得两个同种块相邻需要合并if(last0a[q[i].front()]a[q[last].front()]){// 将当前块的所有剩余水果合并到上一个块中保持顺序while(!q[i].empty()){q[last].push_back(q[i].front());// 从当前块头部取出加入上一个块尾部q[i].pop_front();// 从当前块头部移除}}else{lasti;// 当前块无法合并记录为新的上一个块}}}coutendl;// 输出完当前果篮后换行// 第三步整理块移除空块压缩队列编号intcur0;// cur记录整理后的有效块数量for(inti1;im;i){if(!q[i].empty())// 如果第i个块还有剩余水果q[cur]q[i];// 将其移动到前面压缩编号双端队列可以直接赋值}mcur;// 更新块的数量}return0;}【运行结果】5 1 0 1 1 0 1 2 4 5 3