洛谷 P2278 [HNOI2003]操作系统 题解【堆】【模拟】【贪心】

点击量：212

    这个题主要是细节的锅，包括坑人的题面……

目录

题目描述

写一个程序来模拟操作系统的进程调度。假设该系统只有一个CPU，每一个进程的到达时间，执行时间和运行优先级都是已知的。其中运行优先级用自然数表示，数字越大，则优先级越高。

 

如果一个进程到达的时候CPU是空闲的，则它会一直占用CPU直到该进程结束。除非在这个过程中，有一个比它优先级高的进程要运行。在这种情况下，这个新的（优先级更高的）进程会占用CPU，而老的只有等待。

 

如果一个进程到达时，CPU正在处理一个比它优先级高或优先级相同的进程，则这个（新到达的）进程必须等待。

 

一旦CPU空闲，如果此时有进程在等待，则选择优先级最高的先运行。如果有多个优先级最高的进程，则选择到达时间最早的。

 

输入输出格式

输入格式：

输入包含若干行，每一行有四个自然数（均不超过10^8），分别是进程号，到达时间，执行时间和优先级。不同进程有不同的编号，不会有两个相同优先级的进程同时到达。输入数据已经按到达时间从小到大排序。输入数据保证在任何时候，等待队列中的进程不超过15000个。

 

输出格式：

按照进程结束的时间输出每个进程的进程号和结束时间。

 

输入输出样例

输入样例#1：

1 1 5 3 
2 10 5 1 
3 12 7 2 
4 20 2 3 
5 21 9 4 
6 22 2 4 
7 23 5 2 
8 24 2 4 

输出样例#1：

1 6
3 19
5 30
6 32
8 34
4 35
7 40
2 42

题解：

    这个题一看上去和堆有关系（但是03年的堆并不普及），但是如果新的优先级比较高，就可以把旧的挤出来。这样一来我们就要用一个结构体来存储一个进程还需要多少时间结束。

    事实上，我们用一个时间指针t指向现在的时间，如果下一个要到达的时间晚于现在的时间，那么就从堆里继续执行进程，直到堆空或者下一个要到达的时间在当前进程结束之前。此时把当前进程的剩余时间减小这个“时间差”就可以了，稍微分析一下可以发现，当程序开始执行的那一刻，就已经算作在把剩余时间\(-1\)了，那么计算到下一个时间点的时间差。如果差值大于等于要执行的进程，这个进程就可以被完全执行了。（注意是大于等于，因为时间差实际上是位于两个时间点之间的，拿这两个时间点减的话就没有错了。）

    而题目中说了，相同优先级无法挤掉前面的，这样在堆里可以按编号小的优先排序。再按照上面的步骤从堆中取出元素即可。

Code：

#include<cstdio>
#include<queue>
using std::priority_queue;
struct work
{
    int n,t,p;
    work(int n,int t,int p)
    {
        this->n=n;
        this->t=t;
        this->p=p;
    }
    work(){}
    friend bool operator <(work A,work b)//注意优先级
    {
        if(A.p!=b.p)
            return A.p<b.p;
        return A.n>b.n;
    }
};
priority_queue<work> q;
int main()
{
    int num,u,v,w;
    long long t=0;
    work k;
    while(scanf("%d",&num)!=EOF)
    {
        scanf("%d%d%d",&u,&v,&w);
        while(!q.empty()&&t+q.top().t<=u)//可以被全部执行
        {
            t+=q.top().t;
            k=q.top();
            printf("%d %lld\n",k.n,t);
            q.pop();
        }
        if(q.empty())
            t=u;
        else
        {
            work k=q.top();//执行到最后一刻
            q.pop();
            k.t-=u-t;
            q.push(k);
            t=u;
        }
        q.push(work(num,v,w));
    }
    while(!q.empty())
    {
        k=q.top();
        q.pop();
        t+=k.t;
        printf("%d %lld\n",k.n,t);
    }
    return 0;
}