洛谷 - P2278 - 操作系统 - 模拟

た入场券 2021-09-30 11:06 246阅读 0赞

[https://www.luogu.org/problemnew/show/P2278][https_www.luogu.org_problemnew_show_P2278]  
题目没有说同时到达的优先级最大的应该处理谁。  
讲道理就是处理优先级最大的。

#include<bits/stdc++.h> using namespace std; typedef long long ll; struct Process { int id; int itime; int dtime; int pri; inline bool operator<(const Process& p)const { if(pri==p.pri) //大根堆，大的先出，符号反向 return itime>p.itime; else return pri<p.pri; } inline bool pri_less_than(const Process &p) { return pri<p.pri; } inline void input(int &i,int &it,int &dt,int &p) { id=i; itime=it; dtime=dt; pri=p; } } p,cur; priority_queue<Process> pq; ll curtime,deltatime,pretime,nexttime; void show_state() { printf("ptime=%lld ctime=%lld dtime=%lld\n",pretime,curtime,deltatime); printf(" curid=%d curdtime=%d\n",cur.id,cur.dtime); printf(" pq.size=%d\n",(int)pq.size()); printf("\n"); } void change_process() { if(pq.empty()) return; if(cur.id==0) { //puts("next process!"); cur=pq.top(); pq.pop(); nexttime=curtime+cur.dtime; //show_state(); } else if(cur.pri_less_than(pq.top())) { //puts("change process!"); //命令保存当前进程并取出新进程，更新时间 pq.push(cur); cur=pq.top(); pq.pop(); nexttime=curtime+cur.dtime; //show_state(); } } void do_process() { //puts("do process!"); if(cur.id==0) return; //show_state(); ll mintime=min(deltatime,(ll)cur.dtime); deltatime-=mintime; pretime+=mintime; cur.dtime-=mintime; if(cur.dtime==0) { printf("%d %lld\n",cur.id,pretime); cur.id=0; nexttime=-1; } //show_state(); } void update() { do { do_process(); //当前进程做不完了，堆顶是不是有比它大的？ change_process(); } while(cur.id&&deltatime); //CPU正忙，尽可能从堆里面取出进程 } int main() { #ifdef Yinku freopen("Yinku.in","r",stdin); #endif // Yinku int id,itime,dtime,pri; scanf("%d%d%d%d",&id,&itime,&dtime,&pri); curtime=itime; pretime=itime; deltatime=curtime-pretime; p.input(id,itime,dtime,pri); pq.push(p); update(); while(~scanf("%d%d%d%d",&id,&itime,&dtime,&pri)) { while(cur.id&&itime>nexttime) { //puts("!"); pretime=curtime; curtime=nexttime; deltatime=curtime-pretime; update(); } //puts("?"); if(cur.id==0) pretime=itime; else pretime=curtime; curtime=itime; deltatime=curtime-pretime; p.input(id,itime,dtime,pri); pq.push(p); update(); } pretime=curtime; curtime=1e18; deltatime=curtime-pretime; update(); return 0; }

转载于:https://www.cnblogs.com/Yinku/p/10986410.html

[https_www.luogu.org_problemnew_show_P2278]: https://www.luogu.org/problemnew/show/P2278