题解：P5763 [NOI1999] 内存分配

· · 题解

P5763 [NOI1999] 内存分配题解：

原题链接

题意有些长，可以看样例来想。
具体样例其实可以看这张图：
是不是一目了然。

具体思路：

其实，我们可以看这张图（设红色为已经占用的内存空间，蓝色为未占用的内存空间）。
我们可以瞬间发现，每个蓝色块的长度是上一个红色块的尾和下一个红色块的头之差。
那么，我们可以用一个集合来维护红色块即可。
set<pair<int,int>> s;//first:占内存的起始位置,second:占用内存长度
我们还要一个优先队列来维护最早被结束掉的进程。
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;//first:进程结束时间，second:占内存的起始位置
但是题目中还有一个等待队列要怎么处理呢？
当然用我们最常见的普通队列。
queue<pair<int,int>> waitq;//first:占用内存时间，second:占用内存长度
接着，我们就用这三个东西来维护整个过程即可。

具体求法：

添加进程：

  1. 枚举类似图中每个红色块。
  2. 判断相邻的红色块能不能塞下。
  3. 能塞下，相当于添加一个新的红色块，加入集合和优先队列。
  4. 如果都不行，加入等待队列，同时维护被放入等待队列的元素个数。

释放内存：

  1. 看当前的优先队列顶部。
  2. 结束时间比当前小
  3. 释放，并释放结束时间相同的进程，同时维护最晚释放时间。
  4. 删除这些进程所对应的红色块
  5. 判断等待队列能否加入。

Tips:

  1. 开始时要在 set 中加入 -1 和 n（内存是 0 \sim n-1）的，这样才能保证把开始的红色块算上。
  2. 先释放内存，在加入新进程。
  3. 释放内存时，要记得释放相同时间的进程。
  4. 记得等待队列的优先级比新进程高。

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
set<pair<int,int>> s;//first:占内存的起始位置,second:占用内存长度
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;//first:进程结束时间，second:占内存的起始位置
queue<pair<int,int>> waitq;//first:占用内存时间，second:占用内存长度
int mx,cnt;
bool fang(int t,int x,int y)//在第t个时刻放入占内存长度x，持续时间y
{
    for(auto it=s.begin();it!=s.end();it++)//枚举每一个红色块
    {
        auto j=it;
        j++;
        if(j!=s.end())//细节判断
        {
            if(j->first-it->first-it->second>=x)//两个相邻的红色块的缝隙可以塞下当前进程
            {
                s.insert({it->first+it->second,x});//放入
                q.push({t+y,it->first+it->second});
                return 1;
            }
        }
    }
    return 0;
}
void free(int t)//在时间为t时释放内存
{
    while(!q.empty()&&t>=q.top().first)
    {
        int tt=q.top().first;
        while(!q.empty()&&q.top().first == tt)//有多个进程同时弹出
        {
            auto tmp=q.top();
            q.pop();
            s.erase(s.lower_bound({tmp.second,0}));//记得把set中也删掉（删除这些进程随对应的红色块）
        }
        mx=tt;//记录最晚进程
        while(!waitq.empty())
        {
            if(fang(tt,waitq.front().second,waitq.front().first))//判断等待队列的头能不能加入
            {
                waitq.pop();//能，弹出
            }
            else
            {
                break;//后面的元素不能提前加入
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    s.insert({-1,1});//细节
    s.insert({n,1});
    int t,m,p;
    while(cin>>t>>m>>p&&(t+m+p))
    {
        free(t);//先释放
        if(!fang(t,m,p))//后加入
        {
            waitq.push({p,m});//放不下，加入等待队列
            cnt++;//题目的第二个要求
        }
    }
    free(2e9+10);//可以认为将进程全释放
    cout<<mx<<'\n'<<cnt<<'\n';
    return 0;
}