2018-10-29 02:41

# Jumping the Queue用DP怎么实现？

Problem Description
The beginning of a winter break near Spring Festival is always the beginning of a peak period of transportation. If you have ever tried to get a train ticket at that time, you must have witnessed the endless queues in front of every ticket box window. If a guy has seen his friend in a queue, then it is very much likely that this lucky guy might go straight to his friend and ask for a favor. This is called "jumping the queue". It is unfair to the rest of the people in the line, but, it is life. Your task is to write a program that simulates such a queue with people jumping in every now and then, assume that, if one in the queue has several friends asking for favors, he would arrange their requests in a queue of his own.

Input
There will contain one or more test cases. Each test case begins with the number of groups n (1<= n <=1000). Then n group descriptions follow, each one consisting of the number of friends belonging to the group and those people's distinct names. A group is a friend group. People in one group are friend with each other. A name is a string of up to 4 characters chosen from {A, B, ..., Z, a, b, ..., z}. A group may consist of up to 1000 friends. You may assume that there is no one belong to two different groups.
Finally, a list of commands follows. There are three different kinds of commands:

● ENQUEUE X - Mr. or Ms. X goes into the queue
● DEQUEUE - the first person gets the ticket and leave the queue
● STOP - end of test case

The input will be terminated by a value of 0 for n.

Output
For each test case, first print a line saying "Scenario #k", where k is the number of the test case. Then, for each DEQUEUE command, print the person who just gets a ticket on a single line. Print a blank line between two test cases, but no extra line at the end of output.

Sample Input
2
3 Ann Bob Joe
3 Zoe Jim Fat
ENQUEUE Ann
ENQUEUE Zoe
ENQUEUE Bob
ENQUEUE Jim
ENQUEUE Joe
ENQUEUE Fat
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
2
5 Anny Jack Jean Bill Jane
6 Eva Mike Ron Sony Geo Zoro
ENQUEUE Anny
ENQUEUE Eva
ENQUEUE Jack
ENQUEUE Jean
ENQUEUE Bill
ENQUEUE Jane
DEQUEUE
DEQUEUE
ENQUEUE Mike
ENQUEUE Ron
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
0

Sample Output
Scenario #1
Ann
Bob
Joe
Zoe
Jim
Fat

Scenario #2
Anny
Jack
Jean
Bill
Jane
Eva

• 点赞
• 写回答
• 关注问题
• 收藏
• 邀请回答