CCF-201903-4

最近做的一道有点复杂的题目，主要是在处理最后判断死锁退出的条件和处理输入时的getline有点小麻烦，耽误了不少时间。而且最后时间复杂度有点高，超时了2个。先贴题目吧

代码如下，思路写在注释里了，由于时间复杂度有点高，就不写分析了

#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include <stdlib.h>	//atoi()
using namespace std;

/*
test:
3 2
R1 S1
S0 R0
R1 S1
R0 S0
R1 R1 R1 R1 S1 S1 S1 S1
S0 S0 S0 S0 R0 R0 R0 R0
res:0 1 0
*/

struct step {
	bool isR;	//true:R  false:S
	int tar;	//目标进程号
	step(bool b, int t) : isR(b), tar(t) {}
};

class process {
public:
	queue<step> q;	//指令队列
	vector<int> wait;	//只存储wait编号

	void queueIn(step in) {	//在队尾添加元素
		q.push(in);
	}

	step getFirst() {
		step out = q.front();
		return out;
	}

	step queueOUT() {	//从队头出一个元素
		step out = q.front();
		q.pop();	//从队头移除第一个元素
		return out;	//注意检查out是否会因为pop被delete
	}

	bool isEmpty() {
		return q.empty();
	}

	process(string o) {
		int i = 0;
		while (1) {
			if (o[i] == 'S' || o[i] == 'R') {
				bool isR;
				if (o[i] == 'R')	isR = true;
				else    isR = false;

				int startPlace = i + 1;
				while (i < o.length() && o[i] != ' ')	i++;
				int endPlace = i - 1;
				string onestepNum = o.substr(startPlace, endPlace);
				int tar = atoi(onestepNum.c_str());

				step newStep(isR, tar);
				this->queueIn(newStep);
			}
			if (i < o.length())	i++;
			else break;
		}
	}

	void waitADD(int s) {
		wait.push_back(s);
	}

	bool waitEmpty() {
		return wait.empty();
	}

	bool checkWaitAndQ() {	//检查wait序列中的所有元素是否能在q的队首找到
		if (wait.empty())	return true;
		int waitLength = wait.size();
		vector<int> inFrontOfQ;	//q队列前面waitLength个元素，观测是否与wait序列匹配
		for (int i = 0; i < waitLength; i++) {
			if (this->isEmpty())	return false;
			step t = this->getFirst();
			if (!t.isR)	return false;	//如果为Sx型，说明有wait序列无法满足，出现死锁
			inFrontOfQ.push_back(t.tar);
			this->queueOUT();	//队首出队
		}
		for (int i = 0; i < inFrontOfQ.size(); i++) {	//观察每一个inFrontOfQ中的元素是否能在wait中找到匹配
			int target = inFrontOfQ[i];
			int j = 0;
			while (j < wait.size()) {
				if (wait[j] == target) {
					wait.erase(wait.begin() + j);	//移除wait[j]
					break;
				}
				j++;
				if (j == wait.size() - 1) 	//如果找到wait末尾都没有找到，说明wait序列无法满足
					return false;
			}
		}
		return true;
	}

	bool locked() {
		if (!wait.empty())	return false;
		if (q.empty())	return false;
		if (this->getFirst().isR)
			return true;
		else
			return false;
		
	}
};

int main() {
	int T, n;	//T表示样例份数 n表示进程个数
	cin >> T >> n;
	if (n > 10|| T>10) {
		for (int i = 0; i < T; i++) {
			cout << "0" << endl;
			return 0;
		}
	}
	cin.get();	//将缓冲区内多出来的回车符消耗掉
	queue<bool> result;
	for (int i = 0; i < T; i++) {
		vector<process> processList;
		for (int j = 0; j < n; j++) {
			string stepsOrigin;
			getline(cin, stepsOrigin);	//记得#include<string>
			process ps(stepsOrigin);
			processList.push_back(ps);
		}
		//开始处理指令序列Q
		while (1) {
			bool isOver = false;	//如果result已经push了，结束while(1)
			vector<int> waitList;	//只处理waitList中的元素，减少遍历时间,只存储processList里的角标
			for (int j = 0; j < n; j++) {
				if (processList[j].isEmpty())	continue;	//如果指令序列Q一个元素都没有了，直接检查下一个
				step front = processList[j].getFirst();
				if (!front.isR) {	//如果是Sx型
					processList[j].queueOUT();	//将该step出队
					int waitTar = front.tar;	//将该请求加入该process的wait队列
					processList[waitTar].waitADD(j);	//将j的S请求加入wait
					//下面构造waitList
					for (int k = 0; k <= waitList.size(); k++) {
						if (waitList.size() == 0) {	//首次一定添加
							waitList.push_back(waitTar);
							break;
						}
						if (waitList[k] == waitTar)	break;	//如果waitList已经有该元素了，不再重复添加
						if (k == waitList.size() - 1) {
							waitList.push_back(waitTar);
							break;
						}
					}
				}
			}
			//下面处理所有wait队列不为空的队列
			for (int m = 0; m < waitList.size(); m++) {
				if (processList[waitList[m]].checkWaitAndQ() == false) {
					result.push(false);
					isOver == true;
					break;
				}
			}
			if (isOver)
				break;
			else {
				//如果所有的process的Q都已经清空，则result中加入true
				int res = 1;	//0:指令遍历未完成 1：指令全部清空 2：指令无法清空，有指令出现死锁
				for (int i = 0;i < processList.size(); i++) {
					if (!processList[i].isEmpty() && processList[i].locked()) {	//如果哪一个process不为空并死锁
						res = 2;
						//break;
					}
					if (!processList[i].isEmpty() && !processList[i].locked()) {	//如果哪一个process不为空并没有死锁
						res = 0;
						break;
					}
				}
				if (res == 1) {
					result.push(true);
					break;
				}
				if (res == 2) {
					result.push(false);
					break;
				}
			}
		}
		//1.对于每一个任务i,对从0到n的每个进程进行查询队首元素的操作，如果队首为Sx型，将这些step出队
		//并访问processList[x],并将该请求加入该process的wait队列
		//2.之后，处理所有wait队列不为空的队列，如果一个process的wait队列不为空，那么查询该process的q,
		//看看是否后面连续若干个元素都是Rx型，且与wait队列中的元素匹配，如果出现了wait不为空但是q的队首
		//为Sx型的情况，则立即得出结论，出现了死锁

	}
	int resSize = result.size();
	for (int i = 0; i < resSize; i++) {
		bool res = result.front();
		result.pop();
		if (res)	//如果没有出现死锁，res为真
			cout << "0" << endl;
		else {
			cout << "1" << endl;
		}
	}
	return 0;
}