问题 A: 深入浅出学算法043-排队打水

题目描述

有 $n$ 个人要排队去打水，每个人需要一定的时间 $t_i$ 才能打完水离开。他们按照到达的时间先后排成一列，从前往后依次编号为 $1,2,\cdots,n$。一开始队伍为空。每个人依次进入队伍，如果队伍中有人正在打水，那么这个人就必须站在队伍的末尾等待。每个人打完水后会离开队伍，问每个人离开队伍的时间。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $t_1,t_2,\cdots,t_n$，表示每个人打水所需的时间。

输出格式

输出 $n$ 行，第 $i$ 行表示第 $i$ 个人离开队伍的时间。

数据范围

$1\leq n\leq 1000,1\leq t_i\leq 1000$

输入样例

5
3 6 2 4 3

输出样例

3
9
11
15
18

算法1

(模拟+队列) $O(n)$

模拟整个排队打水的过程。用一个队列 $q$ 来维护当前队伍中等待的人，每当有一个人进入队伍时，先计算出他的离开时间 $t$，然后将他加入队尾。如果队伍中有人正在打水，那么这个人就必须在队伍中等待，所以 $t$ 的计算需要加上队伍中最后一个人的离开时间。

C++ 代码

算法2

(排序+贪心) $O(nlogn)$

对每个人按照到达时间排序，然后依次计算他们的离开时间。用一个变量 $cur$ 来维护当前队伍中最后一个打完水的人的离开时间，每当有一个人进入队伍时，如果他到达的时间比 $cur$ 大，则他可以直接打水离开队伍。否则他必须等待，等待的时间就是 $cur-t_i$，然后再计算他的离开时间。

C++ 代码