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:占用内存长度
接着，我们就用这三个东西来维护整个过程即可。

具体求法：

添加进程：

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

释放内存：

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

Tips:

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

代码：

CPP

#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;
}

题解：P5763 [NOI1999] 内存分配

文章操作