题解：瑞学堂 徐老师的零食分享队列
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】瑞学堂徐老师的零食分享队列【题目描述】徐老师有n nn包零食每包零食有一个美味值a i a_iai。他决定按照一个有趣的规则分享给排成一队的k kk个好朋友。朋友们初始按1 11到k kk编号顺序排队。分享规则如下徐老师每次将当前队首的朋友叫到面前。如果徐老师还有零食就给这位朋友一包零食从剩余零食里按顺序给即第一包给第一个朋友第二包给第二个朋友…这位朋友拿到零食后其编号会加上这包零食的美味值然后重新排到队伍的末尾。如果徐老师没有零食了那么分享结束。你的任务是计算分享结束后队伍中朋友们的编号按从队首到队尾的顺序。假设朋友数量足够多分享过程中不会没有朋友。【输入】第一行两个整数n nn和k ( 1 ≤ n , k ≤ 10 5 ) k (1≤n,k≤10^5)k(1≤n,k≤105)分别表示零食的数量和朋友的数量。第二行包含n nn个整数a 1 , a 2 , . . . , a n ( 1 ≤ a i ≤ 1000 ) a_1,a_2,...,a_n (1≤a_i≤1000)a1,a2,...,an(1≤ai≤1000)表示每包零食的美味值。【输出】输出一行包含k kk个整数表示最终队伍中从队首到队尾的朋友编号用空格隔开。【输入样例】5 3 2 5 1 3 4【输出样例】4 6 11【核心思想】问题分析给定n nn包零食每包美味值为a i a_iai和k kk个按1 11到k kk编号排队的朋友。按顺序将第i ii包零食给当前队首朋友该朋友编号加上a i a_iai后重新排到队尾重复n nn次后输出最终队列。这是一个队列模拟问题关键在于用队列维护队首取出、修改后队尾插入的循环顺序。算法选择队列Queue利用FIFO先进先出特性队首元素出队处理后立即入队到队尾完美模拟循环排队过程顺序遍历按i ii从1 11到n nn的顺序依次分配零食保证第i ii包零食的美味值a i a_iai加到当前队首朋友上关键步骤初始化队列将朋友编号1 11到k kk依次入队形成初始排队顺序模拟分配遍历i ii从1 11到n nn取出队首朋友编号x xxx q.front()并出队q.pop()更新编号x x a i x x a_ixxai加上第i ii包零食的美味值重新入队q.push(x)排到队伍末尾输出结果依次取出队首元素并输出直到队列为空时间/空间复杂度时间复杂度O ( n k ) O(n k)O(nk)初始化队列O ( k ) O(k)O(k)n nn次出队入队操作O ( n ) O(n)O(n)输出O ( k ) O(k)O(k)空间复杂度O ( k ) O(k)O(k)队列中始终最多存储k kk个朋友编号队列模拟的核心思想FIFO 模拟循环结构队列天然支持队首处理、队尾等待的循环逻辑无需手动维护循环数组或取模运算状态更新与重新排队每次处理完一个元素后将其更新后的状态放回队尾保证所有元素按固定周期被处理顺序与轮次的解耦第i ii包零食分配给当前队首而非第i ii个朋友由队列动态决定接收者实现规则与数据的分离适用场景适用于需要按固定规则循环处理元素、且处理顺序由当前状态动态决定的问题如轮询调度、约瑟夫环变体等【算法标签】#队列【代码详解】#includebits/stdc.husingnamespacestd;constintN100005;// 定义数组最大容量为100005intn,k;// n为零食数量k为朋友数量inta[N];// a[i]表示第i包零食的美味值queueintq;// 队列q存储当前排队的朋友编号队首为下一个被叫到的朋友intmain(){cinnk;// 读入零食数量n和朋友数量kfor(inti1;in;i)// 读入每包零食的美味值cina[i];for(inti1;ik;i)// 初始化队列朋友1到k按顺序排队q.push(i);// 将朋友编号i入队// 模拟分享过程依次处理n包零食for(inti1;in;i)// 第i包零食分给当前队首的朋友{intxq.front();q.pop();// 取出队首朋友xxa[i];// 朋友x的编号加上第i包零食的美味值q.push(x);// 该朋友重新排到队伍末尾}// 输出分享结束后队列中朋友的编号从队首到队尾while(!q.empty())// 当队列不为空时{coutq.front() ;// 输出队首朋友的编号q.pop();// 该朋友出队}coutendl;// 输出结束后换行return0;}【运行结果】5 3 2 5 1 3 4 4 6 11
