M27925 小组队列

思路：

考虑维护一个双向链表，链表节点中除当前点的编号外，存储在队列中的上一个点和下一个点和在当前小组中的上一个点和下一个点。
~~好像做麻烦了？~~
之前一直没写过 C++ 指针版的链表啊！于是来写了一发，踩了不少坑 /ll
总的来说，需要注意的地方有：(1) 检查“小组队列”的始末 ahead、atail 和每个小组的末端 ttail[bel] 是否需要更新；(2) 判断指针是否为空。

cpp

#include <iostream>
#include <sstream>

using namespace std;

struct LinkList {
	int id;
	LinkList *aprev;
	LinkList *anext;
	LinkList *tprev;
	LinkList *tnext;
	
	LinkList(int _id) : id(_id), aprev(nullptr), anext(nullptr), tprev(nullptr), tnext(nullptr) {}
};

int team;
LinkList *ahead = nullptr, *atail = nullptr;
int belong[1000000];
LinkList *ttail[50099];

void insert(int x){
	LinkList *cur = new LinkList(x);
	if (belong[x] == 0) belong[x] = ++team;
	if (ttail[belong[x]] == nullptr){
		ttail[belong[x]] = cur;
		cur->aprev = atail;
		if (atail != nullptr) atail->anext = cur;
		atail = cur;
		if (ahead == nullptr) ahead = cur;
	} else {
		LinkList *aft = ttail[belong[x]];
		cur->anext = aft->anext;
		if (aft->anext != nullptr) aft->anext->aprev = cur;
		cur->aprev = aft;
		aft->anext = cur;
		cur->tprev = aft;
		aft->tnext = cur;
		ttail[belong[x]] = cur;
		if (atail == aft) atail = cur;
	}
}

void pop(){
	LinkList *nxt = ahead->anext;
	if (ahead->anext != nullptr){
		ahead->anext->aprev = nullptr;
		ahead->anext = nullptr;
	} else {
		atail = nullptr;
	}
	if (ahead->tnext != nullptr){
		ahead->tnext->tprev = nullptr;
		ahead->tnext = nullptr;
	} else {
		ttail[belong[ahead->id]] = nullptr;
	}
	delete ahead;
	ahead = nxt;
}

void finalize(){
	while (ahead != nullptr){
		LinkList *nxt = ahead->anext;
		delete ahead;
		ahead = nxt;
	}
}

int main(){
	cin >> team;
	getchar();
	for (int i = 1; i <= team; i++){
		int id;
		string line;
		getline(cin, line);
		stringstream scin(line);
		while (scin >> id){
			belong[id] = i;
		}
	}
	while (true){
		string op;
		cin >> op;
		if (op == "STOP") break;
		if (op == "ENQUEUE"){
			int x;
			cin >> x;
			insert(x);
		} else {
			cout << ahead->id << endl;
			pop();
		}
	}
	finalize();
	return 0;
}

M27925 小组队列 ​

M27925 小组队列