Luogu P2278 [HNOI2003]操作系统
题面
原来是道大水题，但是它的题面有点意思，于是我就手残把它加进了解题计划中。
题面描述对于操作系统，我们只拥有一个CPU，只能同时处理一个任务。现在有很多任务需要操作系统解决，它们将按照产生时间输入。
每个任务都需要一定时间完成，并且每个任务都有一个优先级和产生时间。当它们产生时，如果CPU空闲，那么会直接处理这个任务，如果CPU忙碌但当前正在执行的任务的优先级没有它高，会中断当前任务的执行，优先执行该任务。如果上述条件均不满足，该任务会进入等待队列。
对于CPU，当当前任务运行完后将会从队列中取出优先值最高的任务，并且立刻开始运行该任务。并且对于一个被中断的任务，当它被再次运行时只需从中断出开始运行即可，无需重新开始。
分析考虑到CPU在空闲时会从等待队列中取出优先值最高的那个任务开始运行，所以很显然这就是个优先队列。只要让优先队列将优先值最高的那个任务一直放在堆顶就可以了。
对于刚出现的每一个任务，我们直接将它放进队列，然后在下一个任务出现前不断地挨个处理程序。如果一个程序在运行到一半的时候被中断，那么保存剩余运行时间为总运行时间后将它重新压回队列。
代码我们使用结构体来存放每个任务的信息。
struct task
{
int number;//任务编号
int need;//需要时间
int get;//出现时间
int grade;//优先级
inline bool operator gradegrade==b.grade&&this->get>b.get);
}
};
然后是优先队列
std::priority_queue<task,std::vector,std::less> wait;
最后就是主函数了
int main()
{
int num,get,times,grade;
int time=-1;
while(scanf("%d%d%d%d",&num,&get,×,&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;
}
我们最开始使用一个timetimetime来存放当前运行到的时刻。每一次读入一个任务的时候，意味着从time+1time+1time+1时刻到当前出现的一刹那这段时间都不会被打断。在这段时间内我们不断地取出一个任务，并试着完成它，并用最后余留下来的一点时间来完成部分的任务，然后把这个完成一部分的任务放回队列，在此时输入的那组任务就正式出现，我们直接将它放入队列，并且把timetimetime设为当前时刻。然后在所有的任务输入完之后逐个完成剩下所有的任务，就是最后一个while循环所在做的。
这样，这道题就结束了。
本题完整代码
转载自本人Luogu Blog的这篇文章
作者：macesuted
