题解：瑞学堂 徐老师的零食分享队列

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

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

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

【题目来源】

瑞学堂：徐老师的零食分享队列

【题目描述】

徐老师有n nn包零食，每包零食有一个美味值a i a_iai​。他决定按照一个有趣的规则分享给排成一队的k kk个好朋友。

朋友们初始按1 11到k kk编号顺序排队。分享规则如下：

1. 徐老师每次将当前队首的朋友叫到面前。
2. 如果徐老师还有零食，就给这位朋友一包零食（从剩余零食里按顺序给，即第一包给第一个朋友，第二包给第二个朋友…），这位朋友拿到零食后，其编号会加上这包零食的美味值，然后重新排到队伍的末尾。
3. 如果徐老师没有零食了，那么分享结束。

你的任务是，计算分享结束后，队伍中朋友们的编号（按从队首到队尾的顺序）。假设朋友数量足够多，分享过程中不会没有朋友。

【输入】

第一行两个整数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

【核心思想】

1. 问题分析：给定n nn包零食（每包美味值为a i a_iai​）和k kk个按1 11到k kk编号排队的朋友。按顺序将第i ii包零食给当前队首朋友，该朋友编号加上a i a_iai​后重新排到队尾，重复n nn次后输出最终队列。这是一个队列模拟问题，关键在于用队列维护"队首取出、修改后队尾插入"的循环顺序。

2. 算法选择：

   • 队列（Queue）：利用FIFO（先进先出）特性，队首元素出队处理后立即入队到队尾，完美模拟循环排队过程
   • 顺序遍历：按i ii从1 11到n nn的顺序依次分配零食，保证第i ii包零食的美味值a i a_iai​加到当前队首朋友上

3. 关键步骤：

   • 初始化队列：将朋友编号1 11到k kk依次入队，形成初始排队顺序
   • 模拟分配（遍历i ii从1 11到n nn）：
     • 取出队首朋友编号x xx：x = q.front()，并出队q.pop()
     • 更新编号：x = x + a i x = x + a_ix=x+ai​（加上第i ii包零食的美味值）
     • 重新入队：q.push(x)（排到队伍末尾）
   • 输出结果：依次取出队首元素并输出，直到队列为空

4. 时间/空间复杂度：

   • 时间复杂度：O ( n + k ) O(n + k)O(n+k)，初始化队列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个朋友编号

5. 队列模拟的核心思想：

   • FIFO 模拟循环结构：队列天然支持"队首处理、队尾等待"的循环逻辑，无需手动维护循环数组或取模运算
   • 状态更新与重新排队：每次处理完一个元素后，将其更新后的状态放回队尾，保证所有元素按固定周期被处理
   • 顺序与轮次的解耦：第i ii包零食分配给"当前队首"而非"第i ii个朋友"，由队列动态决定接收者，实现规则与数据的分离
   • 适用场景：适用于需要按固定规则循环处理元素、且处理顺序由当前状态动态决定的问题（如轮询调度、约瑟夫环变体等）

【算法标签】

#队列

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=100005;// 定义数组最大容量为100005intn,k;// n为零食数量，k为朋友数量inta[N];// a[i]表示第i包零食的美味值queue<int>q;// 队列q存储当前排队的朋友编号（队首为下一个被叫到的朋友）intmain(){cin>>n>>k;// 读入零食数量n和朋友数量kfor(inti=1;i<=n;i++)// 读入每包零食的美味值cin>>a[i];for(inti=1;i<=k;i++)// 初始化队列：朋友1到k按顺序排队q.push(i);// 将朋友编号i入队// 模拟分享过程：依次处理n包零食for(inti=1;i<=n;i++)// 第i包零食分给当前队首的朋友{intx=q.front();q.pop();// 取出队首朋友xx+=a[i];// 朋友x的编号加上第i包零食的美味值q.push(x);// 该朋友重新排到队伍末尾}// 输出分享结束后队列中朋友的编号（从队首到队尾）while(!q.empty())// 当队列不为空时{cout<<q.front()<<" ";// 输出队首朋友的编号q.pop();// 该朋友出队}cout<<endl;// 输出结束后换行return0;}

【运行结果】

5 3 2 5 1 3 4 4 6 11