主要涉及双端队列和单端队列的使用。
#include <stdio.h> #include <queue> #include <string> #include <cstring> enum StatementType { ASSIGN = 0, PRINT, LOCK, UNLOCK, END }; struct Statement { StatementType type; int var; // varindex int val; }; struct Process { int pid; std::queue<Statement> statements; Process(int pid_) : pid(pid_) {} }; int gTimeCost[5]; int gVars[26]; int gQuantum; bool bLocked = false; std::deque<Process*> readyQueue; std::queue<Process*> blockQueue; bool parseStatement(const std::string& str, Statement& sm) { if(str == "lock") { sm.type = LOCK; return true; } if(str == "unlock") { sm.type = UNLOCK; return true; } if(str == "end") { sm.type = END; return true; } if(str.substr(0, strlen("print ")) == "print ") { sm.type = PRINT; sm.var = str.back() - 'a'; return true; } auto pos = str.find_first_of("="); if(pos != std::string::npos) { sm.type = ASSIGN; sm.var = str.front() - 'a'; sm.val = strtoul(str.substr(pos+1).c_str(), NULL, 10); return true; } return false; } void runProcess(Process* p, int quantum) { while(quantum > 0){ auto sm = p->statements.front(); switch(sm.type) { case PRINT: printf("%d: %d\n", p->pid, gVars[sm.var]); break; case ASSIGN: gVars[sm.var] = sm.val; break; case UNLOCK: { if(!blockQueue.empty()) { auto bp = blockQueue.front(); blockQueue.pop(); readyQueue.push_front(bp); } bLocked = false; } break; case LOCK: if(bLocked) { blockQueue.push(p); return; } else { bLocked = true; } break; case END: return; default: break; } p->statements.pop(); quantum -= gTimeCost[sm.type]; } readyQueue.push_back(p); } int main() { int caseN; scanf("%d", &caseN); while(caseN-- > 0) { memset(gTimeCost, 0, sizeof(gTimeCost)); memset(gVars, 0, sizeof(gVars)); gQuantum = 0; bLocked = false; char emptyline[8]; fgets(emptyline, 8, stdin); int n; scanf("%d%d%d%d%d%d%d", &n, &gTimeCost[0], &gTimeCost[1], &gTimeCost[2], &gTimeCost[3], &gTimeCost[4], &gQuantum); for(int i = 0; i < n; ++i) { Process *p = new Process(i+1); for(;;) { char buf[1024] = {0}; fgets(buf, 1024, stdin); if(buf[strlen(buf)-1] == '\n') buf[strlen(buf)-1] = '\0'; std::string str(buf, strlen(buf)); Statement sm; if(parseStatement(str, sm)) { p->statements.push(sm); if(sm.type == END) break; } } readyQueue.push_back(p); } while(!readyQueue.empty()) { Process* p = readyQueue.front(); readyQueue.pop_front(); runProcess(p, gQuantum); } if(caseN > 0) printf("\n"); } }