消息传递窗口 最近在刷CSP认证2019年三月份的第四题，主体思路是开n个队列，分别去维护n个进程，之前的想法是直接暴力,去判断这n个队列的队首元素是否匹配，本以为没有问题。但是出现了玄学错误，官网测试上报的是超时。 经后面发现是读入挂了。附上原来的读入程序
cin >> T >> n; getchar(); while (T--) { for (int i = 0; i < n; i++) { while(!q[i].empty()) q[i].pop(); } int flag = 0, o = 0; for (int i = 0; i <= 10005; i++) fill(vis[i],vis[i] + 10,0); for (int i = 0; i < n; i++) { do { scanf("%c%d",&tmp.ch,&tmp.num); q[i].push(tmp); }while (getchar()!='\n') }在本地运行是正确的，不懂挂在哪里。 下面附上改进版的读入程序 思路也改进了，之前暴力会T，后面采用了广搜。 具体思想：初始化：取n个队列的队首元素入广搜队列。 然后取出广搜队列里的队首元素，判断其与其他n个进程队列里的队首元素是否匹配，若匹配，则相应进程的两个队列的队首元素均出队，并且需要打上标记。 （没听懂没关系，下面用例子说明） 注意不管匹配不匹配，广搜队列里的队首元素都会出队列。 例：T = 1，n = 2 S1 R0 R0 S1 初始化：广搜队列里有
S1R0取出广搜队列里的队首元素：S1，发现与进程1里的R0相匹配，因此将广搜队列里的R0打上标记，下次遍历到它时，直接跳过；并且将S1,R0分别从原来的进程队列里pop出去，此时应将R0和S1入队列。需要注意的是将程序从进程队列里pop出去时，若进程队列非空的话，需要将进程队列新的队首元素重新入广搜队列。 打上标记的做法用一个vis[a][b]//a表示第几个进程，b表示在进程里的位置 S1(vis[0][0]） R0(vis[0][1]) R0(vis[1][0]) S1(vis[1][1])
但是最终只得了90分，不知道哪里出错了。 希望能帮助到大家。
#include <bits/stdc++.h> using namespace std; struct data { char ch;//字母R/s int num;//R/s后面接的数字 int belong;//属于哪个进程 int pos;//每个进程对应的位置 }; queue<data>q[10005];//每个队列维护相应的进程 queue<data>mq; int vis[10005][10]; char str[20]; int main() { char str[20]; int T, n; data tmp, tmp1; cin >> T >> n; getchar(); while (T--) { for (int i = 0; i < n; i++) { while(!q[i].empty()) q[i].pop(); } int flag = 0, o = 0; for (int i = 0; i <= 10005; i++) fill(vis[i],vis[i] + 10,0); for (int i = 0; i < n; i++) { int number = 0; int ans = 0; gets(str); for (int j = 0; j < strlen(str); j++) { if (str[j] == 'R' || str[j] == 'S') { tmp.ch = str[j]; int p = j + 1; while (str[p] >= '0' && str[p] <= '9') { number += str[p] - '0'; ans = number; number *= 10; p++; } tmp.belong = i; tmp.num = ans; tmp.pos = o++; ans = 0; number = 0; q[i].push(tmp); } } } for (int i = 0; i < n; i++) { tmp = q[i].front(); mq.push(tmp); } while (!mq.empty()) { tmp = mq.front(); mq.pop(); if (vis[tmp.belong][tmp.pos]) continue; if (!q[tmp.num].empty())tmp1 = q[tmp.num].front(); else continue; if ((tmp.ch == 'R' && tmp1.ch == 'S' && tmp1.num == tmp.belong) || (tmp.ch == 'S' && tmp1.ch == 'R' && tmp1.num == tmp.belong)) { q[tmp.num].pop(); if (!q[tmp.num].empty()) mq.push(q[tmp.num].front()); vis[tmp.num][tmp1.pos] = 1; q[tmp.belong].pop(); if (!q[tmp.belong].empty()) mq.push(q[tmp.belong].front()); } } for (int i = 0; i < n; i++) { if (q[i].empty()) flag++; } if (flag == n) printf("0\n");//无死锁 else printf("1\n");//有死锁 } return 0; }