2014
02-10

# Jumping the Queue

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.

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.

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.

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

Scenario #1
Ann
Bob
Joe
Zoe
Jim
Fat

Scenario #2
Anny
Jack
Jean
Bill
Jane
Eva

Hint
You must maintain a hash table to store the names of the people, otherwise the efficiency of your program will not be acceptable since Judge's input file
is as large as about 12.5MB.


题目涉及Caps Lock键的两种状态：关闭和打开。因此可以开一个二维数组，一维表示Caps Lock键关闭，另一维表示Caps Lock键打开。但这里也可以开两个一维数组on[]和off[]分别表示Caps Lock键的两种状态。（此题和算法导论的动态规划章节中的一题双线作业调度类似，那一题也是这样的做法）

if(s[i]>='A'&&s[i]<='Z') {//如果是大写字母
on[i]=min(on[i-1],off[i-1]+1)+1;//从on状态转移到on状态不需要按任何键，直接按字母键即可，从off状态转移到on状态的最少步数是：先按Caps Lock键再按字母键，所以是off[i-1]+1+1;
off[i]=min(on[i-1]+1,off[i-1]+1)+1;//同理~~~
}
else {//如果是小写字母
on[i]=min(on[i-1]+1,off[i-1]+1)+1;//在这种情况下从on状态转移到on状态的最小步数是先按Shift键并按字母键，从off状态转移到on状态的最小步数是先按字母键再按Caps Lock键，所以是off[i-1]+1+1;
off[i]=min(on[i-1]+1,off[i-1])+1;
}

AC代码：

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=105;
int on[N],off[N];
char s[N];
int main()
{
int T,len;
cin>>T;
while(T--){
cin>>s;
len=strlen(s);
if(s[0]>='A'&&s[0]<='Z'){
on[0]=2;off[0]=2;
}
else{
on[0]=2;off[0]=1;
}
for(int i=1;i<len;i++){
if(s[i]>='A'&&s[i]<='Z') {
on[i]=min(on[i-1],off[i-1]+1)+1;
off[i]=min(on[i-1]+1,off[i-1]+1)+1;
}
else {
on[i]=min(on[i-1]+1,off[i-1]+1)+1;
off[i]=min(on[i-1]+1,off[i-1])+1;
}
}
cout<<min(on[len-1]+1,off[len-1])<<endl;
}
return 0;
}

1. 这道题目虽然简单，但是小编做的很到位，应该会给很多人启发吧！对于面试当中不给开辟额外空间的问题不是绝对的，实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟，今天看到小编这篇文章相见恨晚。