P5763 [NOI1999] 内存分配 题解

· · 题解

这是一个没有 log 的方法

蒟蒻参考自这篇题解

题目大意

或许可以放一张图（样例解释）：

需要用到的数据结构：

链表（维护内存空间），队列（维护等待进程），vector（维护已分配内存的进程）

具体思路：

将整个内存空间按照分成若干块，

若空间被进程占用，则单独为一块代表进程；

若空间空闲，则将连续的空闲的内存单元看作一整块，

块与块之间用链表串起来。

链表起初为整个空的内存，之后有进程申请分配 M 的内存时，

从头到尾扫描链表，寻找第一块空闲且长度足够的内存块（设长度为 len )

将这一块分割成前后长度为 M 与 len - M 的两块，

如果没有就丢进等待队列中；

若有进程结束释放内存，则找到它在链表中分配内存的位置，变成一块空闲的，

并与前后有相连的空闲内存块合并

这样我们可以保证 空闲块的个数 不多于 进程块的个数 + 1

所以每次扫描最多需要 O(T) ， T 是输入的行数的时间，

vector用于存已分配内存的进程在链表的位置和结束的时间，

总的时间复杂度约为 O(T^2) ，可通过本题。

实现看代码：

主框架：

w 记录的是目前最早结束的进程结束的时间，在 task_out 的过程中会持续更新

task_out() 用于结束进程，释放内存，并给等待队列中的进程分配内存（因为可以在任意时刻分配，所以要在 t 时刻之前分配内存，达到一有空间就分配的目的）

task_in() 给当前进程分配，如果不行，丢队列里。

tot 统计进入队列的进程个数

len 是持续的时间

while(1)
{
    read(t); read(m); read(len);
    if(!t && !m && !len) break;
    while(t >= w) task_out();  //释放时刻 t 之前的结束进程
    if(!task_in(t, m, len, w)) q.push({m, len}), tot ++ ;
}

定义这么一个链表：

struct Node
{
    int value;  //记录块长
    bool tag;  // 0 为空闲，1 为占用
    Node *Prev, *Next;
};

inline void insert(Node *p, int val, bool op)  //在 p 后添加节点，op（0/1）表示是否空闲
{
    Node *q = new Node();
    q->value = val; q->tag = op;
    p->Next->Prev = q;
    q->Next = p->Next;
    p->Next = q; q->Prev = p;
}

inline void remove(Node *p)  //删除节点 p 
{
    p->Prev->Next = p->Next;
    p->Next->Prev = p->Prev;
    delete p;
}

vector:

用以维护被分配内存的进程的相关信息，

第一维记录结束时间，第二维记录在链表中的位置。

vector<pair<int, Node*>> p;

等待队列

第一维是要分配的大小，第二维是持续的时间。

queue<pair<int, int>> q;

task_in()函数：

inline bool task_in(int t, int m, int len, int &w)
{
    for(Node *it = head->Next; it != tail; it = it->Next)  //扫描链表
    {
        if(it->tag == 0 && it->value >= m)  //空闲 && 空间足够
        {
            int val = it->value; val -= m;  //分割
            Node *last = it->Prev; remove(it);
            insert(last, m, 1); last = last->Next;
            if(val != 0) insert(last, val, 0);  //如果刚好占满就不用分成两块了
            p.push_back({t + len, last}); w = min(w, t + len);  //进入vector中，记录结束时间和位置，更新结束时间最小值
            return true; //分配成功，推出循环
        }
    }
    return false;
}

get_blank()函数：

用来合并空闲的块

inline void get_blank(Node *p)
{
    int val = p->value;
    if(p->Prev != head && p->Prev->tag == 0) val += p->Prev->value, remove(p->Prev);  //向前合并
    if(p->Next != tail && p->Next->tag == 0) val += p->Next->value, remove(p->Next);  //向后合并
    Node *last = p->Prev; remove(p);
    insert(last, val, 0);  //合并成一大块
}

task_out()函数：

inline void task_out()
{
    int wzs = INF;
    for(int i = 0; i < p.size(); i ++ )
    {
        if(p[i].first == w) get_blank(p[i].second), p.erase(p.begin() + i -- );  //释放当前最早结束的，合并，从vector中删除
        else wzs = min(wzs, p[i].first);  //记录其他进程中最早结束的
    }
    while(!q.empty())
    {
        pair<int, int> x = q.front();
        if(!task_in(w, x.first, x.second, wzs)) break; //wzs需要更新其他进程中最早结束的
        q.pop();
    }
    w = wzs;  //释放后最早结束的
}

呼，最后放一下代码吧：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

const int N = 10010;
const int INF = 2e9;

struct Node
{
    int value;
    bool tag;
    Node *Prev, *Next;
};

int n, t, m, len, res, tot, w = INF;
vector<pair<int, Node*>> p;
queue<pair<int, int>> q;
Node *head, *tail;

inline void read(int &x)
{
    int sgn = 1; x = 0;
    char ch = getchar();
    while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if(ch == '-') sgn = -1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = (x << 1) + (x << 3), x += (ch ^ '0'), ch = getchar();
    x *= sgn;
}

inline void insert(Node *p, int val, bool op)
{
    Node *q = new Node();
    q->value = val; q->tag = op;
    p->Next->Prev = q;
    q->Next = p->Next;
    p->Next = q; q->Prev = p;
}

inline void remove(Node *p)
{
    p->Prev->Next = p->Next;
    p->Next->Prev = p->Prev;
    delete p;
}

inline void get_blank(Node *p)
{
    int val = p->value;
    if(p->Prev != head && p->Prev->tag == 0) val += p->Prev->value, remove(p->Prev);
    if(p->Next != tail && p->Next->tag == 0) val += p->Next->value, remove(p->Next);
    Node *last = p->Prev; remove(p);
    insert(last, val, 0);
}

inline bool task_in(int t, int m, int len, int &w)
{
    for(Node *it = head->Next; it != tail; it = it->Next)
    {
        if(it->tag == 0 && it->value >= m)
        {
            int val = it->value; val -= m;
            Node *last = it->Prev; remove(it);
            insert(last, m, 1); last = last->Next;
            if(val != 0) insert(last, val, 0);
            p.push_back({t + len, last}); w = min(w, t + len);
            return true;
        }
    }
    return false;
}

inline void task_out()
{
    int wzs = INF;
    for(int i = 0; i < p.size(); i ++ )
    {
        if(p[i].first == w) get_blank(p[i].second), p.erase(p.begin() + i -- );
        else wzs = min(wzs, p[i].first);
    }
    while(!q.empty())
    {
        pair<int, int> x = q.front();
        if(!task_in(w, x.first, x.second, wzs)) break;
        q.pop();
    }
    w = wzs;
} 

int main()
{
    read(n);
    head = new Node(); tail = new Node();
    head->Next = tail; tail->Prev = head;
    insert(head, n, 0);
    while(1)
    {
        read(t); read(m); read(len);
        if(!t && !m && !len) break;
        while(t >= w) task_out();
        if(!task_in(t, m, len, w)) q.push({m, len}), tot ++ ;
    }
    while(!q.empty()) task_out();
    for(int i = 0; i < p.size(); i ++ ) w = max(w, p[i].first);
    printf("%d\n%d\n", w, tot);
    return 0;
}

END.