UVa 144 Student Grants-开发者社区

题目理解

本题模拟了一种特殊的学生补助金发放系统。政府为了“劝阻”学生接受高等教育，设计了一套复杂的发放流程：

每位学生每年可获得40 4040美元的补助金，在其生日最近的工作日发放。
每天最多有N NN（1 ≤ N ≤ 25 1 \leq N \leq 251≤N≤25）名学生到补助金部门排队领取。
发放使用一台特殊的自动取款机（ATM \texttt{ATM}ATM），机器内部有一个金库（存放大量1 11美元硬币）和一个输出存储区。
机器只在输出存储区为空时，才会从金库向输出存储区补充硬币，且补充规则如下：
1. 早晨开机时，输出存储区为空，立即补充1 11枚硬币。
2. 当这些硬币被取出后，下一次补充2 22枚。
3. 每次补充数量依次增加，直到达到预设上限k kk（1 ≤ 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 40)O(N×40)，对本题规模完全可行。
空间复杂度：使用队列存储学生，为O ( N ) O(N)O(N)。

代码实现

// Student Grants// UVa ID: 144// Verdict: Accepted// Submission Date: 2016-01-21// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structstudent{intid,withdraw;};intmain(){intn,k;while(cin>>n>>k,n||k){queue<student>students;for(inti=1;i<=n;i++)students.push((student){i,0});intcoins=0,remain=0;while(true){intcurrent=(remain>0)?remain:((++coins)>k?(coins=1):coins);if(students.empty())break;student aStudent=students.front();students.pop();if((aStudent.withdraw+current)>=40){remain=aStudent.withdraw+current-40;cout<<setw(3)<<right<<aStudent.id;}else{aStudent.withdraw+=current;students.push(aStudent);remain=0;}}cout<<endl;}return0;}