HDU 5071 Chat （神一般的模拟题）

时间：2019-12-09 11:22:27

关键字： hdu 区域赛

手机看文章

扫描二维码
随时随地手机看文章

[导读]题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5071 题面： Chat Time Limit: 2000/1000 MS (Java/Others

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5071

题面：

Chat Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 2195 Accepted Submission(s): 465

Problem Description As everyone knows, DRD has no girlfriends. But as everyone also knows, DRD’s friend ATM’s friend CLJ has many potential girlfriends. One evidence is CLJ’s chatting record.

CLJ chats with many girls all the time. Sometimes he begins a new conversation and sometimes he ends a conversation. Sometimes he chats with the girl whose window is on the top.

You can imagine CLJ’s windows as a queue. The first girl in the queue is the top girl if no one is “always on top ”.

Since CLJ is so popular, he begins to assign a unique positive integer as priority for every girl. The higher priority a girl has, the more CLJ likes her. For example, GYZ has priority 10⁹, and JZP has priority 10⁸ while Sister Soup has priority 1, and Face Face has priority 2.

As a famous programmer, CLJ leads a group to implement his own WM(window manager). The WM will log CLJ’s operations. Now you are supposed to implement the log system. The general logging format is “Operation #X: LOGMSG.”, where X is the number of the operation and LOGMSG is the logging message.

There are several kinds of operations CLJ may use:

1.Add u: CLJ opens a new window whose priority is u, and the new window will be the last window in the window queue. This operation will always be successful except the only case in which there is already a window with priority u. If it is successful, LOGMSG will be “success”. Otherwise LOGMSG will be “same priority”.

2.Close u: CLJ closes a window whose priority is u. If there exists such a window, the operation will be successful and LOGMSG will be “close u with c”, where u is the priority and c is the number of words CLJ has spoken to this window. Otherwise, LOGMSG will be “invalid priority”. Note that ANY window can be closed.

3.Chat w: CLJ chats with the top window, and he speaks w words. The top window is the first window in the queue, or the “always on top” window (as described below) instead if there exists. If no window is in the queue, LOGMSG will be “empty”, otherwise the operation can be successful and LOGMSG will be “success”.

4.Rotate x: CLJ performs one or more Alt-Tabs to move the x-th window to the first one in the queue. For example, if there are 4 windows in the queue, whose priorities are 1, 3, 5, 7 respectively and CLJ performs “Rotate 3”, then the window’s priorities in the queue will become 5, 1, 3, 7. Note that if CLJ wants to move the first window to the head, this operation is still considered “successful”. If x is out of range (smaller than 1 or larger than the size of the queue), LOGMSG will be “out of range”. Otherwise LOGMSG should be “success”.

5.Prior: CLJ finds out the girl with the maximum priority and then moves the window to the head of the queue. Note that if the girl with the maximum priority is already the first window, this operation is considered successful as well. If the window queue is empty, this operation will fail and LOGMSG must be “empty”. If it is successful, LOGMSG must be “success”.

6.Choose u: CLJ chooses the girl with priority u and moves the window to the head of the queue.This operation is considered successful if and only if the window with priority u exists. LOGMSG for the successful cases should be “success” and for the other cases should be “invalid priority”.

7.Top u: CLJ makes the window of the girl with priority u always on top. Always on top is a special state, which means whoever the first girl in the queue is, the top one must be u if u is always on top. As you can see, two girls cannot be always on top at the same time, so if one girl is always on top while CLJ wants another always on top, the first will be not always on top any more, except the two girls are the same one. Anyone can be always on top. LOGMSG is the same as that of the Choose operation.

8.Untop: CLJ cancels the “always on top” state of the girl who is always on top. That is, the girl who is always on top now is not in this special state any more. This operation will fail unless there is one girl always on top. If it fails, LOGMSG should be “no such person”, otherwise should be “success”.

As a gentleman, CLJ will say goodbye to every active window he has ever spoken to at last, “active” here means the window has not been closed so far. The logging format is “Bye u: c” where u is the priority and c is the number of words he has ever spoken to this window. He will always say good bye to the current top girl if he has spoken to her before he closes it.
Input The first line contains an integer T (T ≤ 10), denoting the number of the test cases.

For each test case, the first line contains an integer n(0 < n ≤ 5000), representing the number of operations. Then follow n operations, one in a line. All the parameters are positive integers below 10⁹.
Output Output all the logging contents.
Sample Input

1 18 Prior Add 1 Chat 1 Add 2 Chat 2 Top 2 Chat 3 Untop Chat 4 Choose 2 Chat 5 Rotate 2 Chat 4 Close 2 Add 3 Prior Chat 2 Close 1
Sample Output

Operation #1: empty. Operation #2: success. Operation #3: success. Operation #4: success. Operation #5: success. Operation #6: success. Operation #7: success. Operation #8: success. Operation #9: success. Operation #10: success. Operation #11: success. Operation #12: success. Operation #13: success. Operation #14: close 2 with 8. Operation #15: success. Operation #16: success. Operation #17: success. Operation #18: close 1 with 11. Bye 3: 2 HintThis problem description does not relate to any real person in THU.
Source 2014 Asia AnShan Regional Contest

解题：

之前一直觉得很烦，没敢写，没想到居然能1A，还是比较惊喜的！

对应8种操作，我采用的数据结构是两个map。第一个map为<(int)pos，(node)n>，其中pos为位置，n为节点，节点中包含两个值u（优先级权值），w（单词数量）。第二个map为<(int)u,(int)pos>其中u为优先级权值，pos为位置，topp存储的是被top的那个对象的优先级，如果为-1，则说明，没有对象处在top状态，sz为当前节点数量。topp和sz都需要时时更新。

1.添加操作，先看是否已经存在（map.count判断），若没有，则添加，否则显示错误信息。

2.关闭操作，看是否存在，若不存在，显示错误信息，否则删除当前节点，并将后面的往上顺移一位。

3.聊天操作，看sz是否为0，若为0，则显示错误信息。若不为0，则看topp是否为-1，若不为-1，则通过map2找到对应位置，更新map1中的值，若为-1，则更新位置为1的map1中的值。

4.置顶操作，首先判断是否越界，不越界则将该位置提到首位即可，其实应该写成函数供下面功能使用，不过好在代码都是差不多的，拷贝下就好了。

5.优先级置顶，循环遍历，然后将该位置置顶，与上同。

6.通过map2找到对应位置，并置顶。

7.将topp值改成此时的u值。

8.将topp还原为-1。

最后要注意还要输出和剩下的没关闭的窗口聊天的数量，若为0，则不需输出，同时要将优先级最高的先输出。

坑点：

1.topp值和sz值需时时维护。

2.数量应用long long保存。

3.输出答案时，最后是有'.'的。

4.最后输出窗口要先输出处于top状态的，没有就按顺序即可。

代码：

#include 
#include 
#include 
#include 
#define LL long long 
using namespace std;
struct node
{
   node (int x,LL y)
   {
	   u=x;
	   w=y;
   }
   node ()
   {
	   u=0;
	   w=0;
   }
   node (const node &xx)
   {
	   u=xx.u;
	   w=xx.w;
   }
   //u优先级权值，w数量
   int u;
   LL w;
};
map  store;
map  refl;
int main()
{
    int t,n,val,sz,pos,topp,uu,maxn;
	LL amt,ww;
	char oper[10];
	scanf("%d",&t);
	node tmp;
	for(int i=1;i<=t;i++)
	{
		store.clear();
		refl.clear();
		sz=0;
		topp=-1;
		scanf("%d",&n);
		for(int j=1;j<=n;j++)
		{
			printf("Operation #%d: ",j);
			getchar();
			scanf("%s",oper);
			//加操作
			if(oper[0]=='A')
			{
				scanf("%d",&val);
                if(!refl.count(val))
				{
					printf("success.n");
                    tmp.w=0;
					tmp.u=val;
                    pos=++sz;
                    refl[val]=pos;
					store[pos]=tmp;
				}
				else
				printf("same priority.n");
			}
			//关闭操作
			else if(oper[0]=='C'&&oper[1]=='l')
			{
				scanf("%d",&val);
				if(!refl.count(val))
				  printf("invalid priority.n");
				else
				{
                  if(val==topp)
					  topp=-1;
                  pos=refl[val];
				  amt=store[pos].w;
                  refl.erase(val);
				  for(int k=pos+1;k<=sz;k++)
				  {
					  uu=store[k].u;
					  store[k-1].u=store[k].u;
					  store[k-1].w=store[k].w;
					  refl[uu]=k-1;
				  }
				  store.erase(sz);
				  sz--;
                  printf("close %d with %d.n",val,amt);
				}
			}
			//聊天功能
			else if(oper[0]=='C'&&oper[2]=='a')
			{
				scanf("%d",&val);
				if(sz==0)
					printf("empty.n");
				else
				{
					printf("success.n");
					if(topp==-1)
						store[1].w+=val;
					else
					{
						pos=refl[topp];
						store[pos].w+=val;
					}
				}
			}
			//置顶操作
			else if(oper[0]=='R')
			{
				scanf("%d",&val);
				if(val<1||val>sz)
					printf("out of range.n");
				else
				{
				   printf("success.n");
                   uu=store[val].u;
				   ww=store[val].w;
				   for(int k=val-1;k>=1;k--)
				   {
                     store[k+1].u=store[k].u;
					 store[k+1].w=store[k].w;
					 refl[store[k+1].u]=k+1;
				   }
				   store[1].u=uu;
				   store[1].w=ww;
				   refl[uu]=1;
				}
			}
			//优先级置顶
			else if(oper[0]=='P')
			{
               if(sz==0)
				   printf("empty.n");
			   else
			   {
				   printf("success.n");
				   maxn=0;
				   for(int k=1;k<=sz;k++)
				   {
					   if(store[k].u>maxn)
						   maxn=store[k].u;
				   }
				   val=refl[maxn];
				   uu=store[val].u;
				   ww=store[val].w;
				   for(int k=val-1;k>=1;k--)
				   {
                     store[k+1].u=store[k].u;
					 store[k+1].w=store[k].w;
					 refl[store[k+1].u]=k+1;
				   }
				   store[1].u=uu;
				   store[1].w=ww;
				   refl[uu]=1;
			   }
			}
			//选择置顶
			else if(oper[0]=='C')
			{
				scanf("%d",&val);
				if(!refl.count(val))
			      printf("invalid priority.n");
				else
				{
					printf("success.n");
					val=refl[val];
 				    uu=store[val].u;
				    ww=store[val].w;
				    for(int k=val-1;k>=1;k--)
				    {
                      store[k+1].u=store[k].u;
					  store[k+1].w=store[k].w;
					  refl[store[k+1].u]=k+1;
				    }
				    store[1].u=uu;
				    store[1].w=ww;
				    refl[uu]=1;
				}
			}
			//top操作
			else if(oper[0]=='T')
			{
				scanf("%d",&val);
				if(!refl.count(val))
                  printf("invalid priority.n");
				else
				{
					printf("success.n");
					topp=val;
				}
			}
			//untop操作
			else if(oper[0]=='U')
			{
                if(topp==-1)
					printf("no such person.n");
				else
				{
					printf("success.n");
					topp=-1;
				}
			}
		}
		//特殊优先级优先
		if(topp!=-1&&store[refl[topp]].w)
			printf("Bye %d: %I64dn",topp,store[refl[topp]].w);
		for(int i=1;i<=sz;i++)
		{
			//优先级只需输出一次
			if(store[i].u!=topp&&store[i].w>0)
				printf("Bye %d: %I64dn",store[i].u,store[i].w);
		}
	}
	return 0;
}