CCF 201903-4消息传递接口(队列)

原题链接

CCF 201903-4消息传递接口

思路

  主要的思路是利用队列来存储每一个进程的收发指令。一旦找到匹配的指令,则将这一对出队列。直到某一次找不到匹配的指令了,退出循环。再判断是不是所有的进程对应的收发指令队列都为空。如果全部为空,则该程序不存在死锁,否则进程存在死锁。
  因为每一个进程有的收发指令的个数是不同的,因此需要处理这样不定数的输入。这里用到了stringstream来进行处理。即

getline(cin,line);//输入一行字符串
stringstream ss(line);
while(ss >> ins){//进行字符串分割。并赋值给ins
      cout<<ins<<endl;
}

  另外还要值得注意的是,进程n的最多可达10的4次方。因此n可能不止一位数,所有在做题的过程中,不能默认每一个收发指令的长度是2。这样就大错特错了!

#include <bits/stdc++.h>
using namespace std;
struct node{
    bool RS;//标记状态,接还是发
    int num;//进程号
    node(bool r,int n){
        RS = r;
        num = n;
    } 
};
int main(){
    int T,n;
    cin>>T>>n;
    getchar();//吃掉换行符 

    while(T--){
        //依次判断T个程序是否存在死锁
        vector<queue<node>> v(n); // 用户存放进程
        string line,ins;
        //初始化各进程的首发指令 
        for(int i=0;i<n;i++){
            getline(cin,line);//输入一行字符串
            stringstream ss(line);
            while(ss >> ins){
//              cout<<ins<<endl;
                bool RS = ins[0] == 'R' ? 0 : 1;//R为0
                //进程号不一定在0-9,所以进程号可能是多位!!! 
                int num = stoi(ins.substr(1));//取出进程号
                v[i].emplace(RS,num);//c++11新特性。相当于v.push(node{RS,num}),比起push内存消耗更少 
//              v[i].push(node{RS,num});//实测这两个好像都可以 
            } 
        }
        bool flag = true;//表示是否有匹配的
        while(flag){
            bool isfind = false; 
            //一直去找匹配的收发指令
            for(int i=0;i<n;++i){
                if(v[i].empty()) continue;
                node tmp = v[i].front();//取出第
                int target = tmp.num;//取出收发指令对应的进程号
                if(!v[target].empty()){//收发指令匹配 
                    if(v[target].front().RS != tmp.RS  && v[target].front().num == i ){
                        v[target].pop();
                        v[i].pop();//出队列 
                        isfind = true;
                    }

                }
            } 
            //找不到匹配的元素了 
            if(isfind == false){
                break;
            }
        }
        flag = true;
        //判断指令全部匹配完。即判断队列是否为空即可
        for (int i=0;i<n;++i){
            if(!v[i].empty()){
                flag = false;
                break;
            }
        }
        if(flag){
            cout<<0<<endl;
        }else{
            cout<<1<<endl;
        }
    }
} 
Tags:

Add a Comment

邮箱地址不会被公开。