写一个程序来模拟操作系统的进程调度。假设该系统只有一个CPU,每一个进程的到达时间,执行时间和运行优先级都是已知的。其中运行优先级用自然数表示,数字越大,则优先级越高。如果一个进程到达的时候CPU是空闲的,则它会一直占用CPU直到该进程结束。除非在这个过程中,有一个比它优先级高的进程要运行。在这种情况下,这个新的(优先级更高的)进程会占用CPU,而老的只有等待。如果一个进程到达时,CPU正在处理一个比它优先级高或优先级相同的进程,则这个(新到达的)进程必须等待。一旦CPU空闲,如果此时有进程在等待,则选择优先级最高的先运行。如果有多个优先级最高的进程,则选择到达时间最早的。
输入文件包含若干行,每一行有四个自然数(均不超过108),分别是进程号,到达时间,执行时间和优先级。不同进程有不同的编号,不会有两个相同优先级的进程同时到达。输入数据已经按到达时间从小到大排序。输入数据保证在任何时候,等待队列中的进程不超过15000个。
1 #include<bits/stdc++.h>
2 using namespace std;
3
4 inline void read(int& x)
5 {
6 x=0;
7 register char f=getchar(),c=0;
8 while(!isdigit(f)&&f!='-')f=getchar();if(f=='-')c=1,f=getchar();
9 while(isdigit(f))x=x*10+(f^48),f=getchar();if(c)x=~x+1;
10 }
11
12 struct node{
13 int nu;
14 int wt;
15 int pr;
16 }a;
17 bool operator < (const node b,const node c)
18 {
19 if(b.pr!=c.pr)
20 {
21 return b.pr<c.pr;
22 }
23 return b.nu>=c.nu;
24 }
25 priority_queue<node>q;
26 int n,t,aa,b,c,d;
27
28 int main()
29 {
30 while(~scanf("%d%d%d%d",&aa,&b,&c,&d))
31 {
32 while(!q.empty())
33 {
34 a=q.top();
35 q.pop();
36 if((t+a.wt)<=b)
37 {
38 t+=a.wt;
39 printf("%d %d\n",a.nu,t);
40 }
41 else
42 {
43 a.wt-=(b-t);
44 q.push(a);
45 break;
46 }
47 }
48 a.pr=d;
49 a.nu=aa;
50 a.wt=c;
51 q.push(a);
52 t=b;
53 }
54 while(!q.empty())
55 {
56 a=q.top();
57 q.pop();
58 t+=a.wt;
59 printf("%d %d\n",a.nu,t);
60 }
61 return 0;
62 }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!!
点击进行留言回复
网友评论