【日常学习】【双端队列】 Uva - 210 Concurrency Simulator题解

雨点打透心脏的1/2处 2022-08-07 01:55 137阅读 0赞

ruka也的确是个小恶魔一般的东西，双端队列竟然只提了一句让我们自己去查TUT比人痛心疾首学习了众多网上神犇们的文章，终于知道了个大概。有几篇整理得非常精妙的文章，在这里给大家分享一下。

[http://blog.163.com/zhoumhan\_0351/blog/static/399542272010358491361/][http_blog.163.com_zhoumhan_0351_blog_static_399542272010358491361]这篇文章相对有些生硬，但是基本系统的介绍了一下双端队列。

[http://hi.baidu.com/xuehuo\_0411/item/f72d5120d5006ad0a517b6b8][http_hi.baidu.com_xuehuo_0411_item_f72d5120d5006ad0a517b6b8]这篇用例子介绍了一下， 和上一篇基本没什么区别。

**[http://www.cnblogs.com/silence250627170/archive/2011/07/24/2115692.html][http_www.cnblogs.com_silence250627170_archive_2011_07_24_2115692.html]在这里我要强烈推荐的是这篇文章，整合了其他几篇文章的内容，详实周到，非常有用，****其中也很好的总结了vector，list和deque的优势和不足。**

**那么我自己来简单总结一下双端队列deque的应用：**

**1.创建时，和其他容器一样的格式，如deque<int> a; 也可以限定元素个数和内容，详细见上述网页；注意要使用头文件deque**

**2.常用函数：**

**a.push\_front() a.push\_back() a.pop\_front() a.pop\_back()从队首或队尾入队或出队**

**3.除了正向的iterator，还可反向遍历deque双端队列中元素迭代器：   
（1）reverse\_iterator rbegin() 注意是rbegin 此时迭代器默认指向队尾，使用it++实际上是向前移动  
（2）reverse\_iterator rend()   **

接下来是这次的例题Concurrency Simulator 并行程序模拟

题目来源：ACM-ICPC World Finals 1991 - San Antonio；Uva-210

这道例题说实话有些惭愧，刚开始并不能完全理解，也不知从何下手，读了本站Devin老师的程序，才明白怎么回事。

这个程序给我的意外惊喜是，原来**i/o/iostream头文件里已经包含了string头文件内容 我不太明白这是怎么回事 有知道的大大请解释一下**

二话不说上代码

#include<iostream>//里面包含string及其函数
    #include<deque>
    #include<cstring>
    using namespace std;
    
    deque<int> ready,block;
    int var[26],id[1024],st[5],program,q,t,i;//关于这一段请看下面
    string code[1024];//存储指令内容
    bool locked;
    
    void run(int i){
    	int time=q;
    	while (time>0){
    		string now=code[id[i]];
    		if(now[2] == '='){  
                var[now[0] - 'a'] = isdigit(now[5]) ? (now[4]-'0')*10+(now[5]-'0') : now[4]-'0';  //isdigit检查是否为数字，var依次存储a,b,c等变量当前值
                time -= st[0];  
            }  
            else if(now[2] == 'i'){  
                cout<<i+1<<": "<<var[now[6]-'a']<<endl;  
                time -= st[1];  
            }  
            else if(now[2] == 'c'){  
                if(locked){block.push_back(i);return;}  
                locked = true;  
                time -= st[2];  
            }  
            else if(now[2] == 'l'){  
                if(!block.empty()) ready.push_front(block.front()),block.pop_front();   
                time -= st[3];  
                locked = false;  
            }  
            else if(now[2] == 'd'){return ;}  
            id[i]++;  
        }  
        ready.push_back(i);
    }
    
    int main(){
    	cin>>t;
    	while (t--){
    		cin>>program>>st[0]>>st[1]>>st[2]>>st[3]>>st[4]>>q;
    		memset(var,0,sizeof(var));  
            ready.clear();block.clear();  
            int line_num = 0;
    		for (i=0;i<program;i++){
    			ready.push_back(i);
    			getline(cin,code[line_num++]);
    			id[i]=line_num-1;
    			while (code[line_num-1]!="end"){
    				getline(cin,code[line_num++]);
    			} 
    		}
    		locked=false;
    		while (!ready.empty()){
    			int now=ready.front();ready.pop_front();
    			run(now);
    		}
    		if(t) cout<<endl;
    	}
    	return 0;
    }

程序是简单的模拟，更多的注释我写在了Devin老师的程序里

int main(){  //ready是排队队列，里面存着每个程序的序号，block是阻止队列，同样存着每个程序序号 
        freopen("1.txt","r",stdin);
    	freopen("2.txt","w",stdout); 
        int T;  //code是指令数组字符串类型，全部程序依次排列，id存储的是每个程序（的序号）对应的第一个指令序号，指令序号在code里 
        cin>>T;  
        while(T--){  
            scanf("%d%d%d%d%d%d%d",&program,&ans[0],&ans[1],&ans[2],&ans[3],&ans[4],&Q);  
            memset(var,0,sizeof(var));  
            ready.clear();block.clear();  
            int line_num = 0;//cin.get(); 好像没意义 //一组数据中全程都用一个line_num不清零 
            for(int i = 0; i < program ;i++){//可能有很多组数据，每个数据有很多个程序，每个程序有很多个指令。T是数据组数，program是程序数，Q是额定时间  
                ready.push_back(i);  // 对于每组数据的每个程序，首先将程序序号压入队尾 
                getline(cin,code[line_num++]);  //读入第一个指令，放到 code中第line_num个位置，并将line_num加一 
                id[i] = line_num-1;  //第0个程序的id是该程序第一个指令在code中的编号 line_num-1今后称“原指令序号” 
                while(code[line_num-1]!="end")  //原指令序号对应的指令不为end时 
                    getline(cin,code[line_num++]);//读入新指令，并将num_line加一，其他不变，只变指令数组  
            }  
            Lock = false;  
            while(!ready.empty()){  
                int now = ready.front();ready.pop_front(); //如果排队队列不为空，就让now等于排队队列中第一个程序序号，同时出队 
                run_program(now);  //运行 
            }  
            if(T)cout<<endl;  //还有其他几组数据就输出空格 
        }  
        return 0;

notepad++可真是个好东西，能把乱码的汉字变成可以显示的O(∩\_∩)O~

**原程序中的cin.get好像没有意义啊，有谁能解释一下？**

——白日射金阙，虎豹九关开

[http_blog.163.com_zhoumhan_0351_blog_static_399542272010358491361]: http://blog.163.com/zhoumhan_0351/blog/static/399542272010358491361/
[http_hi.baidu.com_xuehuo_0411_item_f72d5120d5006ad0a517b6b8]: http://hi.baidu.com/xuehuo_0411/item/f72d5120d5006ad0a517b6b8
[http_www.cnblogs.com_silence250627170_archive_2011_07_24_2115692.html]: http://www.cnblogs.com/silence250627170/archive/2011/07/24/2115692.html