核心内容摘要
《R星每日大赛》：不只是游戏，更是燃擎梦想的赛场！
题目理解本题模拟了一种特殊的学生补助金发放系统。
政府为了“劝阻”学生接受高等教育设计了一套复杂的发放流程每位学生每年可获得40 4040美元的补助金在其生日最近的工作日发放。
每天最多有N NN1 ≤ N ≤ 25 1 \leq N \leq 251≤N≤25名学生到补助金部门排队领取。
发放使用一台特殊的自动取款机ATM \texttt{ATM}ATM机器内部有一个金库存放大量1 11美元硬币和一个输出存储区。
机器只在输出存储区为空时才会从金库向输出存储区补充硬币且补充规则如下早晨开机时输出存储区为空立即补充1 11枚硬币。
当这些硬币被取出后下一次补充2 22枚。
每次补充数量依次增加直到达到预设上限k kk1 ≤ k ≤ 40 1 \leq k \leq 401≤k≤40然后重置为1 11继续循环。
学生依次插入学生卡机器将输出存储区的所有硬币支付给学生并更新卡上记录的总金额。
如果学生累计领取金额不足40 4040美元则取卡重新排到队尾。
如果本次支付后累计金额超过40 4040美元则仅支付至刚好40 4040美元剩余硬币留在输出存储区给下一位学生该学生离开队伍。
需要计算所有学生离开队列的顺序。
解题思路这是一个典型的队列模拟问题。
我们可以将整个过程分解为以下步骤初始化学生队列每个学生用结构体表示包含id初始排队顺序和withdraw已领取金额。
模拟硬币发放循环维护变量coins表示当前应发放的硬币数量按1 , 2 , … , k , 1 , 2 , … 1, 2, \dots, k, 1, 2, \dots1,2,…,k,1,2,…循环。
维护变量remain表示上一位学生领取后输出存储区剩余的硬币数如果刚好40 4040美元则remain 0如果超出则remain为超出部分留给下一位学生。
每次处理队首学生计算本次可领取的硬币数current若remain 0则直接使用remain否则从coins循环中取下一个值并更新coins若超过k kk则重置为1 11。
若该学生withdraw current 40则支付至刚好40 4040该学生离开记录其id并更新remain withdraw current - 40。
否则该学生withdraw current重新入队尾remain 0。
输出离开顺序按离开顺序输出学生编号每个编号占3 33个字符宽度右对齐。
算法复杂度时间复杂度最坏情况下每个学生可能需要多次排队才能领满40 4040美元但总支付次数不超过N × 40 N \times 40N×40因此为O ( N × 40 ) O(N \times
O(N×
对本题规模完全可行。
空间复杂度使用队列存储学生为O ( N ) O(N)O(N)。
代码实现// Student Grants// UVa ID: 144// Verdict: Accepted// Submission Date:
// UVa Run Time:
000s//// 版权所有C2016邱秋。
metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structstudent{intid,withdraw;};intmain(){intn,k;while(cinnk,n||k){queuestudentstudents;for(inti1;in;i)students.push((student){i,0});intcoins0,remain0;while(true){intcurrent(remain