题意:给一个操作和一个话题,操作有, new(加入新话题), reply(某话题置顶,同时当作新话题 ), tag(把某话题标记为旧话题), serach(从top到bottom输出前100个新话题)。
解法: 话题存在一个双向链表中(方便删除和插入), 每个话题名称映射一个链表的节点(用map),然后就是模拟。
坑点: 一个话题可以被tag多次,导致一开始访问了空指针(如果用链表做注意)。
//code
#include<iostream> #include<cstdio> #include<string> #include<list> #include<map> using namespace std; struct List{ List *prev; List *next; string name; friend bool operator < (List a, List b) { return a.name<b.name; } }; int main() { int n; while(cin>>n) { map<string, List*>_m; map<string, List*>::iterator it; List *_l, *Head; Head = new List; _l = new List; _l->name = "Last"; _l->next = NULL; _l->prev = Head; Head->next=_l; Head->name = "Head"; Head->prev = NULL; for(int i=0; i<n; i++) { string tmp; cin>>tmp; if(tmp == "new") { cin>>tmp; List *_l_tmp; _l_tmp = new List; _l_tmp->name = tmp; _l_tmp->next = Head->next; _l_tmp->prev = Head; Head->next = _l_tmp; _l_tmp->next->prev = _l_tmp; _m.insert(map<string, List*>::value_type(_l_tmp->name, _l_tmp)); } else if(tmp == "reply") { cin>>tmp; it = _m.find(tmp); if(it == _m.end()) continue; List *Prev, *Next; Prev = it->second->prev; Next = it->second->next; if(Prev != NULL && Next != NULL) { Prev->next = Next; Next->prev = Prev; } it->second->next = Head->next; it->second->prev = Head; Head->next = it->second; it->second->next->prev = it->second; } else if(tmp == "tag") { cin>>tmp; it = _m.find(tmp); if(it == _m.end()) continue; if(it->second->next == NULL && it->second->prev == NULL) continue; List *Prev, *Next; Prev = it->second->prev; Next = it->second->next; Prev->next = Next; Next->prev = Prev; it->second->next = it->second->prev = NULL; } else if(tmp == "search") { List *q; q = Head->next; int Sum=0; while(q->next != NULL) { cout<<q->name<<endl; Sum++; if(Sum >= 100) break; q = q->next; } cout<<"###"<<endl; } } printf("\n"); } return 0; }