[BZOJ1216]&&[HNOI2003] 操作系统

2014-12-09
竞赛题解 / 基本数据结构
BZOJHNOI

描述 Description

写一个程序来模拟操作系统的进程调度。假设该系统只有一个 CPU，每一个进程的到达时间，执行时间和运行优先级都是已知的。其中运行优先级用自然数表示，数字越大，则优先级越高。如果一个进程到达的时候 CPU 是空闲的，则它会一直占用 CPU 直到该进程结束。除非在这个过程中，有一个比它优先级高的进程要运行。在这种情况下，这个新的（优先级更高的）进程会占用 CPU，而老的只有等待。如果一个进程到达时，CPU 正在处理一个比它优先级高或优先级相同的进程，则这个（新到达的）进程必须等待。一旦 CPU 空闲，如果此时有进程在等待，则选择优先级最高的先运行。如果有多个优先级最高的进程，则选择到达时间最早的。

输入格式 InputFormat

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

输出格式 OutputFormat

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

样例输入 SampleInput

1 1 1 9
2 1 3 10
3 1 2 11
4 1 1 12
5 1 9 13
6 1 10 14
7 2 4 7
8 3 8 4
9 3 4 5
10 3 9 6

样例输出 SampleOutput

6 11
5 20
4 21
3 23
2 26
1 27
7 31
10 40
9 44
8 52

BZOJ 1216

用个优先队列来模拟。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
struct data
{
    int id,arr,las,lev,hav;
    bool operator <(const data& temp) const
    {
        return (lev==temp.lev)?(arr>temp.arr):(lev<temp.lev);
    }
};
data now,a;
priority_queue <data> q;
int main()
{
    while (!q.empty()) q.pop();
    scanf("%d%d%d%d",&t,&x,&y,&z);
    now=(data){t,x,y,z,x};
    while (scanf("%d%d%d%d",&t,&x,&y,&z)!=EOF)
    {
        a=(data){t,x,y,z,x};
        t=now.hav+now.las;
        if (t<=a.arr)
        {
            printf("%d %d\n",now.id,t);
            while (!q.empty() && t<a.arr)
            {
                now=q.top();q.pop();
                if (t+now.las<=a.arr)
                {
                    t+=now.las;
                    printf("%d %d\n",now.id,t);
                }
                else
                {
                    now.las-=a.arr-t;
                    q.push(now);
                    t=a.arr;
                }
            }
        }
        else
        {
            now.las-=a.arr-now.hav;
            q.push(now);
            t=a.arr;
        }
        q.push(a);
        now=q.top();q.pop();
        now.hav=max(t,now.hav);
    }
    while (!q.empty())
    {
        t=now.hav+now.las;
        printf("%d %d\n",now.id,t);
        now=q.top();q.pop();
        now.hav=max(t,now.hav);
    }
    printf("%d %d\n",now.id,now.hav+now.las);
    return 0;
}