题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5071
解题报告:一个管理聊天窗口的程序,一共有八种操作,然后要注意的就是Top操作只是把编号为u的窗口标记为一种特殊的状态,在这种特殊的状态下优先级是最高的,聊天都是跟这个聊,而这个窗口并没有在实际上被提到最前面.还有就是每句后面都有句号.我本来可以1A的,但就是因为没看这个,所以一直WA也找不到原因.
暴力模拟就可以了,因为点最多只有5000个,不会超时,维护一个队列就可以了,但我为了方便判断是不是已经存在还用了一个map容器.
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<map> 6 #include<set> 7 #include<deque> 8 using namespace std; 9 10 deque<int> que; 11 deque<int>::iterator iter; 12 map<int,int> mp; 13 14 int T,n,x,top,istop; 15 void Add() 16 { 17 scanf("%d",&x); 18 if(mp[x] == 0) 19 { 20 que.push_back(x); 21 mp[x] = -1; //因为map查找没有时返回是0,为了避免冲突,初始化为-1 22 puts("success."); 23 } 24 else puts("same priority."); 25 } 26 27 void Close() 28 { 29 scanf("%d",&x); 30 if(mp[x] ) 31 { 32 if(mp[x] > 0) printf("close %d with %d. ",x,mp[x]); 33 else printf("close %d with 0. ",x); 34 if(istop && top == x) istop = 0; // 关掉always状态的就要把这个标记取消掉,不然会出错,但是注释掉也过了,说明没有关掉always状态的操作 35 //但个人觉得还是加上比较好,因为这个操作可以关掉一切存在的 窗口,不加这个可以过就是测试数据的问题了 36 for(iter = que.begin();iter != que.end();++iter) 37 if(*iter == x) 38 { 39 que.erase(iter); 40 break; 41 } 42 mp.erase(x); 43 } 44 else puts("invalid priority."); 45 } 46 void Chat() 47 { 48 scanf("%d",&x); 49 int t; 50 if(que.empty()) 51 { 52 puts("empty."); 53 return ; 54 } 55 if(istop) t = top; //如果存在always top 56 else t = *que.begin(); 57 if(mp[t] == -1) mp[t] = x; 58 else mp[t] += x; 59 puts("success."); 60 } 61 void Rotate() 62 { 63 scanf("%d",&x); 64 if(x > que.size()) 65 { 66 puts("out of range."); 67 return ; 68 } 69 int t = x - 1; 70 iter = que.begin(); 71 while(t--) iter++; 72 t = *iter; 73 que.erase(iter); 74 que.push_front(t); 75 puts("success."); 76 } 77 void Prior() 78 { 79 if(que.empty()) 80 { 81 puts("empty."); 82 return ; 83 } 84 deque<int>::iterator M = que.begin(); 85 for(iter = que.begin();iter != que.end();++iter) 86 if(*M < *iter) M = iter; 87 int t = *M; 88 que.erase(M); 89 que.push_front(t); 90 puts("success."); 91 } 92 void Choose() 93 { 94 scanf("%d",&x); 95 if(mp[x] == 0) 96 { 97 puts("invalid priority."); 98 return ; 99 } 100 for(iter = que.begin();iter != que.end();++iter) 101 if(*iter == x) 102 break; 103 que.push_front(x); 104 que.erase(iter); 105 puts("success."); 106 } 107 void Top() 108 { 109 scanf("%d",&x); 110 if(mp[x] == 0) 111 { 112 puts("invalid priority."); 113 return ; 114 } 115 istop = 1; 116 top = x; 117 puts("success."); 118 } 119 void Untop() 120 { 121 if(istop == 0) 122 { 123 puts("no such person."); 124 return ; 125 } 126 istop = 0; 127 puts("success."); 128 } 129 130 int main() 131 { 132 // freopen("in","r",stdin); 133 char oper[10]; 134 scanf("%d",&T); 135 while(T--) 136 { 137 scanf("%d",&n); 138 mp.clear(); 139 que.clear(); 140 istop = 0; //是否存在top 141 int kase = 1; 142 while(n--) 143 { 144 scanf("%s",oper); 145 printf("Operation #%d: ",kase++); 146 if(!strcmp(oper,"Add")) Add(); 147 else if(!strcmp(oper,"Close")) Close(); 148 else if(!strcmp(oper,"Chat")) Chat(); 149 else if(!strcmp(oper,"Rotate")) Rotate(); 150 else if(!strcmp(oper,"Prior")) Prior(); 151 else if(!strcmp(oper,"Choose")) Choose(); 152 else if(!strcmp(oper,"Top")) Top(); 153 else if(!strcmp(oper,"Untop")) Untop(); 154 } 155 if(istop != 0 && mp[top] > 0) 156 { 157 printf("Bye %d: %d ",top,mp[top]); 158 mp.erase(top); 159 for(iter = que.begin();iter != que.end();++iter) 160 if(*iter == top) break; 161 que.erase(iter); 162 } 163 while(!que.empty()) 164 { 165 if(mp[*que.begin()] > 0) 166 printf("Bye %d: %d ",*que.begin(),mp[*que.begin()]); 167 mp.erase(*que.begin()); 168 que.pop_front(); 169 } 170 } 171 return 0; 172 }