「Luogu P2278」[HNOI2003]操作系统 解题报告

题面

一道模拟题，模拟CPU的处理过程？！省选模拟题

思路：

模拟退火大法+优先队列乱搞

要注意的点

1、空闲时，CPU要处理进程

2、当队列中没有进程时，要先进行判断，然后访问

3、当优先级高的进程替换掉原进程时，原进程已经处理过的时间要减去

4、结束进程时要更新后面进程的时间

既然是模拟题，那就不讲具体了h^ovny：我懒

Code：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int i,S,l,p;
    node(int a,int b,int c,int d):i(a),S(b),l(c),p(d){  }
    node(){ }
    bool operator<(const node X) const{//重载
        if(p!=X.p)
            return p<X.p;
        return S>X.S;
    }
}Now,cur;//Now表示当前处理的进程
int i,S,l,p;
priority_queue<node>P;
int main()
{
    int i;
    scanf("%d%d%d%d",&i,&S,&l,&p);//预先读入一组
    Now=node(i,S,l,p);
    while(~scanf("%d%d%d%d",&i,&S,&l,&p))
    {
        while(Now.S+Now.l<=S&&!P.empty())//中间空闲时间先处理掉
        {
            printf("%d %d\n",Now.i,Now.S+Now.l);
            cur=P.top();P.pop();
            if(cur.S<Now.S+Now.l)//计算影响
                cur.l+=Now.S+Now.l-cur.S;
            Now=cur;
        }
        if(Now.S+Now.l<=S)//如果队列空了，Now就没有输出
        {
            printf("%d %d\n",Now.i,Now.S+Now.l);
            Now=node(i,S,l,p);
            continue;
        }
        if(p>Now.p)//更高级的任务
        {
            Now.l=Now.l+Now.S-S;
            P.push(Now);
            Now=node(i,S,l,p);
            continue;
        }
        P.push(node(i,S,l,p));
    }
    printf("%d %d\n",Now.i,Now.S+Now.l);//队列中还有进程，但Now无法被更新
    while(!P.empty())//弹出队列中的进程
    {
        cur=P.top();P.pop();
        if(cur.S<Now.S+Now.l)//前面进程对当前的影响
            cur.l+=Now.l+Now.S-cur.S;
        printf("%d %d\n",cur.i,cur.S+cur.l);
        Now=cur;
    }
    return 0;
}

「Luogu P2278」[HNOI2003]操作系统 解题报告

原文：https://www.cnblogs.com/hovny/p/10175628.html