题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5071
解题报告:一个管理聊天窗口的程序,一共有八种操作,然后要注意的就是Top操作只是把编号为u的窗口标记为一种特殊的状态,在这种特殊的状态下优先级是最高的,聊天都是跟这个聊,而这个窗口并没有在实际上被提到最前面.还有就是每句后面都有句号.我本来可以1A的,但就是因为没看这个,所以一直WA也找不到原因.
暴力模拟就可以了,因为点最多只有5000个,不会超时,维护一个队列就可以了,但我为了方便判断是不是已经存在还用了一个map容器.
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<deque>
using namespace std; deque<int> que;
deque<int>::iterator iter;
map<int,int> mp; int T,n,x,top,istop;
void Add()
{
scanf("%d",&x);
if(mp[x] == )
{
que.push_back(x);
mp[x] = -; //因为map查找没有时返回是0,为了避免冲突,初始化为-1
puts("success.");
}
else puts("same priority.");
} void Close()
{
scanf("%d",&x);
if(mp[x] )
{
if(mp[x] > ) printf("close %d with %d.\n",x,mp[x]);
else printf("close %d with 0.\n",x);
if(istop && top == x) istop = ; // 关掉always状态的就要把这个标记取消掉,不然会出错,但是注释掉也过了,说明没有关掉always状态的操作
//但个人觉得还是加上比较好,因为这个操作可以关掉一切存在的 窗口,不加这个可以过就是测试数据的问题了
for(iter = que.begin();iter != que.end();++iter)
if(*iter == x)
{
que.erase(iter);
break;
}
mp.erase(x);
}
else puts("invalid priority.");
}
void Chat()
{
scanf("%d",&x);
int t;
if(que.empty())
{
puts("empty.");
return ;
}
if(istop) t = top; //如果存在always top
else t = *que.begin();
if(mp[t] == -) mp[t] = x;
else mp[t] += x;
puts("success.");
}
void Rotate()
{
scanf("%d",&x);
if(x > que.size())
{
puts("out of range.");
return ;
}
int t = x - ;
iter = que.begin();
while(t--) iter++;
t = *iter;
que.erase(iter);
que.push_front(t);
puts("success.");
}
void Prior()
{
if(que.empty())
{
puts("empty.");
return ;
}
deque<int>::iterator M = que.begin();
for(iter = que.begin();iter != que.end();++iter)
if(*M < *iter) M = iter;
int t = *M;
que.erase(M);
que.push_front(t);
puts("success.");
}
void Choose()
{
scanf("%d",&x);
if(mp[x] == )
{
puts("invalid priority.");
return ;
}
for(iter = que.begin();iter != que.end();++iter)
if(*iter == x)
break;
que.push_front(x);
que.erase(iter);
puts("success.");
}
void Top()
{
scanf("%d",&x);
if(mp[x] == )
{
puts("invalid priority.");
return ;
}
istop = ;
top = x;
puts("success.");
}
void Untop()
{
if(istop == )
{
puts("no such person.");
return ;
}
istop = ;
puts("success.");
} int main()
{
// freopen("in","r",stdin);
char oper[];
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
mp.clear();
que.clear();
istop = ; //是否存在top
int kase = ;
while(n--)
{
scanf("%s",oper);
printf("Operation #%d: ",kase++);
if(!strcmp(oper,"Add")) Add();
else if(!strcmp(oper,"Close")) Close();
else if(!strcmp(oper,"Chat")) Chat();
else if(!strcmp(oper,"Rotate")) Rotate();
else if(!strcmp(oper,"Prior")) Prior();
else if(!strcmp(oper,"Choose")) Choose();
else if(!strcmp(oper,"Top")) Top();
else if(!strcmp(oper,"Untop")) Untop();
}
if(istop != && mp[top] > )
{
printf("Bye %d: %d\n",top,mp[top]);
mp.erase(top);
for(iter = que.begin();iter != que.end();++iter)
if(*iter == top) break;
que.erase(iter);
}
while(!que.empty())
{
if(mp[*que.begin()] > )
printf("Bye %d: %d\n",*que.begin(),mp[*que.begin()]);
mp.erase(*que.begin());
que.pop_front();
}
}
return ;
}