P2278操作系统题解

· · 题解

这么标准的优先级，很明显这个题就是用堆来维护每一个程序的处理时间了。

不过本题有个要求，就是cpu空闲时，如果有多个优先级最高的进程，则选择到达时间最早的。也就是指当优先级相等时，使id最小的处于堆顶。

由于stl优先队列堆默认是大跟堆（即最大的在堆顶），那么只需要将默认的小于号在判断时改成大于号就变成小根堆了。

struct node
{
    int id,ti,le;
    //在本题分别对应进程号、剩余执行时间、优先级。
    bool operator < (const node &a) const
    {
        if(le==a.le) return id>a.id;//id更小的在堆顶
        else return le<a.le;//优先级跟高的在堆顶
    }
｝
priority_queue<node>heap;

由于把到达时间最早看成执行时间最短送出一血

那么会造堆后，剩下的就是模拟了。

为了方便，可以在每次程序达到的时候进行一次性处理cpu（及堆里）里的以前未处理的程序，那么可以定义一个变量为now,cuse，第一个是目前处理某一数据处于的时间，第二个为在now和到达新程序之间可以使用的时间。每次处理堆顶程序的时候判断cuse和该程序的ti，如果now>=ti,也就是说在到达新程序之前这个程序就已经处理完毕了，输出id和now，并更新now和cuse，now=now+ti，cuse=cuse-ti，然后再进行判断下一个堆顶。

如果now<it,那么就让目前堆顶处理时间减去now，使now=0，now=当前时间点。

当所有程序都到达完毕后，那么就直接按堆的顺序输出就可以了。

蜜汁码风的代码：

#include<bits/stdc++.h>
using namespace std;

int read(){
    char c=getchar();int a=0;bool f=0;
    while(c<'0'||c>'9'){if(c=='-') f=1;c=getchar();}
    while(c>='0'&&c<='9') a=(a<<1)+(a<<3)+(c^48),c=getchar();
    return f?-a:a;
}
int pr(int a)
{
    if(a<0){putchar('-');a=-a;}
    if(a>=10) pr(a/10);
    putchar(a%10+'0');
}
struct node
{
    int id,ti,le;
    bool operator < (const node &a) const
    {
        if(le==a.le) return id>a.id;
        else return le<a.le;
    }
    node(int id,int ti,int le):id(id),ti(ti),le(le){}
    node(){}
};
priority_queue<node>heap; 
int i,now=0,cuse=0,t,ti,le;
node it;
bool f=0;
int main()
{
    while(scanf("%d",&i)!=EOF)
    {
        t=read(),ti=read(),le=read(),cuse=(t-now);
        if(!heap.empty()) it=heap.top();
        while(!heap.empty()&&cuse>=it.ti&&now+it.ti<=t)
        {
            now+=it.ti;
            cuse-=it.ti;
            pr(it.id);putchar(' ');pr(now);putchar('\n');
            heap.pop();
            if(!heap.empty()) it=heap.top();
        }
        if(!heap.empty()&&cuse)
        {
            it=heap.top();
            heap.pop();
            heap.push(node(it.id,it.ti-cuse,it.le));
        }
        heap.push(node(i,ti,le));
        now=t;
    }
    while(!heap.empty())
    {
        it=heap.top();
        pr(it.id);putchar(' ');pr(now+it.ti);putchar('\n');
        now+=it.ti;
        heap.pop();
    }
}