大家好，我是小黄呀。

VJ题目传送门

题目大意

题目给出n个程序，其中每个程序包含若干条指令，每条指令执行所需时钟周期，给出每个程序拥有的总共时钟周期数，模拟出程序执行的过程，输出相应的信息。

五条指令如下：

var = constant:赋值，其中var为单个小写字母表示，初始为0，是全局变量。constant为小于100的非负整数，是常数。print var:打印lock：上锁，独占资源。unlock：解锁end：程序结束

程序模拟过程中存在两个队列：

rq：等待队列，按此队列依次执行rb：阻止队列，当程序1执行lock时，若程序2再次执行lock，则将程序2放入rb队列中，直到程序执行unlock后，再将rb队列的队首插入到rq队列队首

思路分析

由于lock和unlock指令的具体执行过程，违反了基本队列的规则，具体有两种方法。

自定义一个支持“首部插入”的队列利用STL中的双端队列deque

具体代码及分析

方法一：自定义一个支持“首部插入”的队列 template<class T1,class T2> struct pair：pair可以将两个类合二为一，成为一组数据，相当于一个结构体。更多详细内容 #include<bits/stdc++.h> #define CLOSE() ios::sync_with_stdio(false) #define CLEAR(a,b) memset(a,b,sizeof(a)) #define IN() freopen("in.txt","r",stdin) #define OUT() freopen("out.txt","w",stdout) using namespace std; const int maxn=1e3; using LL=long long; using UI=unsigned int ; //----------------------------------------- vector<vector<string> >prog; vector<pair<int,int> > rf; int readyq[maxn],rrear,rfront; int blocked[maxn],brear,bfront; int main() { #ifdef _DEBUG IN(); OUT(); #endif // _DEBUG int T; scanf("%d",&T); while(T--) { int n,time[5],qutm;//n个程序，每条指令所需的时钟周期，总时钟周期 scanf("%d",&n); for(int i=0;i<5;++i) scanf("%d",&time[i]); scanf("%d",&qutm); getchar(); prog.clear(); rf.clear(); CLEAR(readyq,0); rrear=rfront=0; for(int i=0;i<n;i++)//存入每个程序的指令 { readyq[rfront++]=i; string s; while(getline(cin,s)) { prog.push_back(vector<string>()); rf.push_back(make_pair(0,0)); prog[i].push_back(s); if(s=="end")break; } } CLEAR(blocked,0); brear=bfront=0; map<char,int> vari; bool lock=false; while(rrear!=rfront)//准备队列非空 { int nowprog = readyq[rrear++]; readyq[rfront++] = nowprog; //printf("now = %d\n", nowprog+1); int t = qutm; while (t > 0) //在时间范围内 { string inst = prog[nowprog][rf[nowprog].first++]; int p = inst.find('='), p2 = inst.find("print"); if (inst == "end") { rfront--; break; } else if (p != -1) { vari[inst[p - 2]] = atoi(inst.substr(p + 2).c_str()); t -= time[0]; } else if (p2 != -1) { char va = inst[p2 + 6]; printf("%d: %d\n", nowprog + 1, vari[va]); t -= time[1]; } else if (inst == "lock") { if (!lock) { lock = true; t -= time[2]; } else { rfront--; blocked[bfront++] = nowprog; rf[nowprog].first--; break; } } else { t -= time[3]; lock = false; if (brear != bfront) { readyq[--rrear] = blocked[brear++]; } } } } if (T) puts(""); } return 0; } 方法二：STL中的双端队列deque（先贴的最简洁的，但不好懂） string::nops:作为string的成员函数的一个长度参数时，表示“直到字符串接受结束”。更多详细内容gets与fgets：gets函数没有指定输入字符大小，会无限读取，一旦输入的字符大于数据长度会发生内存越界。fgets函数最多只能读入n-1个字符，读入结束后，系统自动在最后加‘\0’，并以str作为函数值返回。更多详细内容 #include<bits/stdc++.h> using namespace std; const int maxn=1e3; int T,a[7];//测试用例个数，输入的第二行所给起始条件 string s,ans; int main() { cin>>T; for(int i=0;i<T;i++) { for(int j=0;j<7;j++) scanf("%d",&a[j]); getchar();//吸收多余字符 queue<string> q1[a[0]];//每个程序对应的指令 deque<int> qr;//等待队列 queue<int> qb;//阻止队列 for(int j=0;j<a[0];j++)//存入n个程序 { while(getline(cin,s)&&s!="end") q1[j].push(s); qr.push_back(j); } if(i!=0)//连续输出的空行 puts(""); map<string,string> vmp;//变量对应的值 bool isLock=false;//标记是否上锁 while(!qr.empty())//判断等待队列非空 { int t=0,k=qr.front();//t为已消耗的时长，k为当前程序的编号 qr.pop_front(); bool isBlock=false;//标记是否发生上锁未解开 while(t<a[6]&&!q1[k].empty())//判断未超时 { s=q1[k].front();//取首指令 int j=s.find('='); if(j!=string::npos)//赋值 { vmp[s.substr(0,j-1)]=s.substr(j+2); t+=a[1]; } else { j=s.find(' '); if(j!=string::npos)//打印并输出 { ans="0"; if(vmp[s.substr(j+1)]!="") ans=vmp[s.substr(j+1)]; printf("%d: %s\n",k+1,ans.c_str()); t +=a[2]; } else { if(s[0]=='l')//lock { if(!isLock) { isLock=true; t+=a[3]; } else//已上锁 { qb.push(k);//加入阻止队列尾部 isBlock = true;//上锁 break;//跳出 } } else if(s[0]=='u')//unlock { isLock = false;//解锁 if(!qb.empty())//阻止队列非空 { qr.push_front(qb.front());//阻止队列首部加入等待队列首部 qb.pop(); } t+=a[4]; } } } q1[k].pop(); } if(!q1[k].empty()&&isBlock)//再次加入等待队列等待 { qr.push_back(k); } } } return 0; }