刷PAT的过程中遇到了两类排队问题,这里总结一下

• 所有人在同一时刻到达,如1014 Waiting in Line
• 每个人到达的时刻不同,如1017 Queueing at Bank)

解决这类问题一个比较好的思路是递推.
对同一时刻到达的问题,可以每个窗口设置front和rear两个变量,分别表示队首和队尾离队时间.front值最小的队列就是应该插入的队列.入队元素的离队时间可以由rear+=current.duration递推给出.队首元素离队后,原来第二个元素成为新的队首元素.更新front+=header.duration.

对到达时刻不同的问题,给队列设置一个finish,表示完成服务的时间.顾客来排队时,先找最小finish的队列.如果finish比他来的时间还早,那么他不需要等待,直接入队就好.更新finish为current.time+current.duration;如果finish比他来的时间晚,首先要等待finish-current.time这么久的时间.更新finish+=current.duration.

看懂了柳神的解法,再看自己1014的解法,十分惭愧.要继续努力啊🤠