Luogu P2278 [HNOI2003]操作系统

题面

原来是道大水题，但是它的题面有点意思，于是我就手残把它加进了解题计划中。

题面描述

对于操作系统，我们只拥有一个CPU，只能同时处理一个任务。现在有很多任务需要操作系统解决，它们将按照产生时间输入。

每个任务都需要一定时间完成，并且每个任务都有一个优先级和产生时间。当它们产生时，如果CPU空闲，那么会直接处理这个任务，如果CPU忙碌但当前正在执行的任务的优先级没有它高，会中断当前任务的执行，优先执行该任务。如果上述条件均不满足，该任务会进入等待队列。

对于CPU，当当前任务运行完后将会从队列中取出优先值最高的任务，并且立刻开始运行该任务。并且对于一个被中断的任务，当它被再次运行时只需从中断出开始运行即可，无需重新开始。

分析

考虑到CPU在空闲时会从等待队列中取出优先值最高的那个任务开始运行，所以很显然这就是个优先队列。只要让优先队列将优先值最高的那个任务一直放在堆顶就可以了。

对于刚出现的每一个任务，我们直接将它放进队列，然后在下一个任务出现前不断地挨个处理程序。如果一个程序在运行到一半的时候被中断，那么保存剩余运行时间为总运行时间后将它重新压回队列。

代码

我们使用结构体来存放每个任务的信息。

struct task
{
    int number;//任务编号
    int need;//需要时间
    int get;//出现时间
    int grade;//优先级
    inline bool operator < (const task &b) const
    {//给优先队列提供的运算符，我们会将优先级高的，或者是优先级相同但来的更早的任务放到堆顶
        return this->grade<b.grade||(this->grade==b.grade&&this->get>b.get);
    }
};

然后是优先队列

std::priority_queue<task,std::vector<task>,std::less<task>> wait;

最后就是主函数了

int main()
{
    int num,get,times,grade;
    int time=-1;
    while(scanf("%d%d%d%d",&num,&get,&times,&grade)!=EOF)
    {
        while((!wait.empty())&&time+wait.top().need<=get)
        {
            time+=wait.top().need;
            printf("%d %d\n",wait.top().number,time);
            wait.pop();
        }
        if(!wait.empty())
        {
            task cache=wait.top();
            wait.pop();
            cache.need-=get-time;
            wait.push(cache);
        }
        wait.push({num,times,get,grade});
        time=get;
    }
    while(!wait.empty())
    {
        time+=wait.top().need;
        printf("%d %d\n",wait.top().number,time);
        wait.pop();
    }
    return 0;
}

我们最开始使用一个来存放当前运行到的时刻。每一次读入一个任务的时候，意味着从时刻到当前出现的一刹那这段时间都不会被打断。在这段时间内我们不断地取出一个任务，并试着完成它，并用最后余留下来的一点时间来完成部分的任务，然后把这个完成一部分的任务放回队列，在此时输入的那组任务就正式出现，我们直接将它放入队列，并且把设为当前时刻。然后在所有的任务输入完之后逐个完成剩下所有的任务，就是最后一个while循环所在做的。

这样，这道题就结束了。

本题完整代码

---

转载自本人Luogu Blog的这篇文章