1216: [HNOI2003]操作系统

Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 751  Solved: 419

[][][]

Description

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

Input

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

Output

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

Sample Input

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

Sample Output

1 6

3 19

5 30

6 32

8 34

4 35

7 40

2 42

分析：其实这道题就是一道简单的模拟题，但是涉及到时间和优先度的关系，所以要用特殊的数据结构来模拟，因为先是按照优先度来执行，所以想到优先队列，先按照时间排序所有进程，但是发现题目已经将所有进程排好序了，所以一个一个读入即可,接下来做的操作只有两种：1.执行当前进程到下一个进程的到达时间（当前进程的优先度低），2.执行完当前进程，用优先队列模拟即可.

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;struct node{    int id, bg, t, quan;    bool operator < (const node &x) const    {        if (quan != x.quan)            return quan < x.quan;        return bg > x.bg;    }};priority_queue 
           
             q;int id, bg, t, quan, T = 0;int main(){ while (~scanf("%d%d%d%d", &id, &bg, &t, &quan)) { while (!q.empty() && T < bg) { node temp = q.top(); q.pop(); if (T < temp.bg) T = temp.bg; int s = min(bg - T, temp.t); T += s; temp.t -= s; if (temp.t) q.push(temp); else printf("%d %d\n", temp.id, T); } node a; a.id = id; a.bg = bg; a.t = t; a.quan = quan; q.push(a); } while (!q.empty()) { node temp = q.top(); q.pop(); printf("%d %d\n", temp.id,T += temp.t); } return 0;}