洛谷 2278 bzoj 1276 [HNOI2003]操作系统 题解

发表于 | 更新于 | 阅读次数：
本文字数： 887 字 | 阅读时长 ≈ 3 分钟

题意简述

你有一个CPU和若干（<=15000）个进程。每个进程有四个参数：代号，到达时间，运行时间，优先级。输入顺序保证按照到达时间排序。你会先处理先到达的任务。但是当你处理一个任务到一半的时候，来了一个优先级更高的任务，那么你会把刚刚那个任务放一半，处理优先级高的任务，再回来继续处理刚刚那个任务。这时候如果再被打断，那就要在搁置一会。

就这样操作下去。按照结束时间的顺序，输出每个任务的代号，以及它结束的时间。

思路框架

开优先队列维护。先处理掉时间不冲突的任务，然后把时间冲突的任务分成两半，把后面一半再放会优先队列里面。由于时间自然有序，优先队列要先比较优先级，再比较开始时间。

具体思路

我们记录一个时间戳T，表示当前考虑到的时间。那么如果我们发现某个任务完成了，那么它的结束时间就是T了。输出即珂。

我们在线做，也就是说，我们不断输入进程，不断做。不实际保存。

对于新输入的进程a，我们不断找优先级最大并且在a之前就结束掉的任务。我们把它完成，并计算出它的结束时间。输出即珂（没错，边输入边输出）。

如果这个时候还有任务在队列中留着，那么我们把它和a重叠的部分单独切出来，然后重新入一次队列。删除原来那个任务。

关于如何切出来这个任务：
设这个任务是t。
一张丑图:
其中黄色的部分就是我们t被a占用的，切出来留着后面处理的部分。它的长度是T+t.len-a.st。其它的保持不变就好了。

输入完之后，肯定还有被我们切出来的任务还没有处理。我们按优先级处理它们就好了。

代码

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
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 155555
    #define lovelive long long 
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    struct task
    {
        int id,st,len,pri;
        bool operator<(const task &a) const
        {
            if (pri==a.pri) return st>a.st;
            else return pri<a.pri;
        }
    };

    void Input()
    {
        //none
    }

    priority_queue<task> Q;
    void Soviet()
    {
        lovelive Time=0; //时间戳
        task a;
        while(~scanf("%d%d%d%d",&a.id,&a.st,&a.len,&a.pri)) //在线做
        {
            while(!Q.empty() and Time+Q.top().len<=a.st)
            {
                task tmp=Q.top();Q.pop();
                Time+=tmp.len;
                printf("%d %lld\n",tmp.id,Time);
            }
            if (!Q.empty())
            {
                task tmp=Q.top();Q.pop(); //去掉原来的
                tmp.len=tmp.len+Time-a.st;  
                Q.push(tmp); //切出来的重新入队列
            }
            Q.push(a);
            Time=a.st; //更新一下时间戳
        }

        while(!Q.empty()) //处理切出来的部分
        {
            task tmp=Q.top();Q.pop();
            Time+=tmp.len;
            printf("%d %lld\n",tmp.id,Time);
        }
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main(){
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w