并行程序模拟（Concurrency Simulator,ACM/ICPC World Finals 1991,UVa210）题解

Dear 丶 2022-12-28 07:21 120阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入
     *  输出
 *  原题（PDF）
 *   *  案例分析
     *  算法分析
     *  解题标程
     *  错题总结

--------------------

# 题目描述 #

你的任务是模拟n个程序（按输入顺序编号为1~n）的并行执行。  
每个程序包含不超过25条语句，格式一共有5种：var=constant（赋值）；print var（打印）；lock；unlock；end。

变量用单个小写字母表示，初始值为0，为所有程序公有（因此在一个程序里对某个变量赋值可能会影响到另一个程序）。常数是小于100的非负整数。

每个时刻只能有一个程序处于运行态，其他程序均处于等待。上述五种语句分别需要t1、t2、t3、t4、t5单位时间。运行态的程序每次最多运行Q个单位时间（称为配额）。当一个程序的配额用完之后，把当前语句（如果存在）执行完之后该程序会被插入一个等待队列中，然后处理器从队首取出一个程序继续执行。

初始等待队列包含按输入顺序排列的各个程序，但由于lock和unlock语句的出现，这个序列可能会改变。 lock的作用是申请对所有变量的独占访问。lock和unlock总是成对出现，并且不会嵌套。lock总是在unlock的前面。当一个程序成功执行完lock指令后，其他程序一旦试图执行lock指令，就会马上被放到一个所谓的阻止队列的尾部（没有用完的配额就浪费了），当unlock指令执行完毕后，阻止队列的第一个程序进入等待队列的首部。

有多组输入输出数据，输入kase,n、t1、t2、t3、t4、t5、Q，按照时间顺序输出所有print语句的程序编号和结果。

## 输入 ##

1
    3 1 1 1 1 1 1
    a = 4
    print a
    lock
    b = 9
    print b
    unlock
    print b
    end
    a = 3
    print a
    lock
    b = 8
    print b
    unlock
    print b
    end
    b = 5
    a = 17
    print a
    print b
    lock
    b = 21
    print b
    unlock
    print b
    end

## 输出 ##

1: 3
    2: 3
    3: 17
    3: 9
    1: 9
    1: 9
    2: 8
    2: 8
    3: 21
    3: 21

--------------------

# 原题（PDF） #

![1][]

--------------------

## 案例分析 ##

根据输入数据可知：  
一组数据，三个程序块。  
赋值"="，输出"print"，封锁"lock"，解锁"unlock"，结束"end"，五个指令的运行时间为1,1,1,1,1  
而整个程序的配额为1。  
因此可以看出每一个程序块最多只能执行一个语句。  
由此可以得出此过程：

> 第一程序块 “a = 4”  
> 第二程序块 “a = 3”  
> 第三程序块 “b = 5”  
> 第一程序块 “print a”  
> …

这才得到第一个1: 3。

那么**输出格式很简单的可以看出就是程序块的次序加上输出语句**，第一个程序块，输出a的值为3

## 算法分析 ##

根据题意可以看出，有两个队列需要我们去维护：等待队列和封存队列。

*  等待队列即要在首部放入元素，又要在尾部，因此需要用一个 **“双端队列”进行维护（即STL中的deque容器）**
 *  封存队列，因为lock的存在，同时只有在第二次碰到lock时，需要在封存队列的尾部放入元素，因此**封存队列可以为普通的队列（即STL中的queue容器）**

注意：

*  测试数据中可以会出现26个小写字母都被赋值的情况，因此要想办法存这26个小写字母所对应的值，可以使用word\[26\]做一个表格来维护。
 *  等待队列中存放的应该是程序块的编号，同时封存队列中应该存的也是程序块的编号，而命令我们需要将所有命令按照程序块的编号进行分类存放，每一块的命令存到一起。
 *  还要用一个标志来记录lock的状态，应对lock和unlock的不同状态
 *  这里我们用命令串的第3个字符作为标志符号：赋值"="，输出"i"，封锁"c"，解锁"l"

## 解题标程 ##

#include <iostream>
    #include <queue>
    #include <vector>
    #include <cstdio>
    #include <string>
    #include <cstring>
    using namespace std;
    
    int n,t1,t2,t3,t4,t5,q; //输入
    deque<int> wait1;   //等待队列
    queue<int> stop1;   //封存队列
    vector<string> cmd[1005];   //命令
    bool lock1=false;   //记录封存情况
    int t[5];           //记录运行时间
    int now[1005];      //当前程序运行的位置
    int word[26];       //各字母存的数值
    
    //输入函数
    void input()
    {
        
        scanf("%d",&n);
        
        for(int i=0;i<5;i++)
            scanf("%d",&t[i]);
        scanf("%d",&q);
    }
    
    //处理程序块函数
    void solve(int i)
    {
        
        int left=q;   //记录剩余的配额
        string ss;
        
        while(left>0){
          //如果配额小于等于零就证明无法再执行任何的操作
            ss=cmd[i][now[i]];  //ss串中存放上一次执行到的命令串（第一次就是0号命令串）
            //赋值（值只会是一位数或者两位数）
            if(ss[2]=='='){
        
                int v;
                v=ss[4]-'0';  //一位数的情况
                if(ss.size()==6) v=(ss[4]-'0')*10+ss[5]-'0';  //两位数的情况
                word[ss[0]-'a']=v;  //在word中将字母和值相对应
                left-=t[0];   //求出剩余的配额
            }
            //输出"print"
            else if(ss[2]=='i'){
        
                printf("%d: %d\n",i,word[ss[6]-'a']);
                left-=t[1];   //求出剩余的配额
            }
            //封锁"lock"
            else if(ss[2]=='c'){
        
                left-=t[2];   //求出剩余的配额
                
                //只有当封锁状态时，再执行"lock"，就会把这个程序块放到阻止队列的尾部
                if(lock1){
        
                    stop1.push(i);  //把这个程序块放到阻止队列的尾部
                    return; //该程序直接结束，进入下一程序
                }
                else lock1=true;  //若是解锁状态就将状态改为封锁
            }
            //解锁"unlock"
            else if(ss[2]=='l'){
        
                left-=t[3];   //求出剩余的配额
                lock1=false;  //解锁
                if(!stop1.empty()){
         //将封闭队列的首位元素放到等待队列的首位
                    int k;
                    k=stop1.front();      //取出封存队列的首位元素
                    stop1.pop();          //删除封存队列首位元素
                    wait1.push_front(k);  //将封存队列的首位元素放到等待数列的首位
                }
            }
            //结束"end"
            else
                return;
            ++now[i]; //最后还要将程序块中的命令串的行数下移，使得程序块执行下一个指令
        }
        wait1.push_back(i); //循环进行，这个程序块完了再插到尾部
    }
    
    int main(int argc, const char * argv[]) {
        
        int kase;   //多组案例
        scanf("%d",&kase);
        
        while(kase--){
        
            input();  //输入
            
            //对每一块程序块下的命令进行分块存放
            string s;
            for(int i=1;i<=n;i++){
        
                cmd[i].clear();
                while(getline(cin, s)){
           //整行读入（可以读入空格）
                    if(s=="") continue;   //样例中会出现""这种情况需要单独处理
                    cmd[i].push_back(s);  //cmd[i]中存放的就是第i个程序块中的命令
                    if(cmd[i].back()=="end") break; //当存到"end"就退出
                }
                wait1.push_back(i); //一开始的程序块就是顺序存放
            }
            
            memset(now, 0, sizeof(now));
            memset(word,0,sizeof(word));
    
            while(!wait1.empty()){
            //等待队列不为空就循环
                //取出等待队列的首元素去执行“命令”
                int k=wait1.front();  
                wait1.pop_front();  //删除首位元素
                solve(k);
            }
            
            if(kase) puts("");  //题目案例bug
        }
        return 0;
    }

--------------------

## 错题总结 ##

*  cpp中的string可以用getline(cin,s)直接读入整行的字符串（可以读入空格）
 *  deque“双端队列”和queue“普通队列”以及动态数组“vector”的使用方法

[1]: /images/20221120/b9ade4cd89824ff482afd771877ba868.png