洛谷P2278「HNOI2003」题解

发表于 | 评论数： | 阅读次数：

模拟 +优先队列优化

双倍经验

题目描述

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

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

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

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

输入输出格式

输入格式

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

输出格式

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

INPUT & OUTPUT’s examples

Input’s e.g. #1

1
2
3
4
5
6
7
8
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

Output’s e.g. #1

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

说明

$$a,b,c,d \leq 10^8$$

等待队列中的进程不超过$15000$个。

分析

一开始还以为这是个MoveToEx题目。

首先肯定能想到纯模拟的暴力做法，但显然会T到飞起。

我们考虑维护一个优先队列。

重载小于运算符：我们对于两个工作，首先按照优先级排序，如果优先级相等则按到达CPU的顺序排序。

那么我们每输入一个进程，如果现在已经不存在可以被完成的工作，也就是说当前的工作只能被完成一部分时，那么完成这个部分，并更新所需要的时间。

也就是说，我们每输入一个进程，如果当前最紧急（优先级最高）的进程和之前完成进程所用的时间之和$\leq$下一个进程到达的时间，那么更新所需要的时间，并输出答案。

如果不满足这个条件，那么我们把完成队头进程的时间更新为下一个进程到达的时间和总时间的差，然后把它重新加入队列。

最后把输入的数据组合并加入队列，继续循环。

对于在输入过程结束后，还没有被完成的进程，利用优先队列排序后从队头按次序输出即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
struct Node{
    int serial,time,prior;
};
Node first;
bool operator <(Node x,Node y){
    if(x.prior != y.prior){return x.prior<y.prior;}
    return x.serial>=y.serial;
}
std::priority_queue<Node> Q;
int a,b,c,d,NowTime;
/* functions */
inline Node Add_Node(int a,int b,int c,int d){
    Node rt = (Node){a,c,d};
    return rt;
}
int main(int argc,char *argv[]){
    while(scanf("%d%d%d%d",&a,&b,&c,&d) != EOF){
        while(!Q.empty()){
            first = Q.top();
            Q.pop();
            if(NowTime + first.time <= b){
                NowTime += first.time;
                printf("%d %d\n",first.serial,NowTime);
            }
            else{
                first.time -= (b - NowTime);
                Q.push(first); break;
            }
        }
        first = Add_Node(a,b,c,d);
        Q.push(first); NowTime = b;
    }
    while(!Q.empty()){
        first = Q.top();
        Q.pop();
        NowTime += first.time;
        printf("%d %d\n",first.serial,NowTime);
    }
    return 0;
}

THE END