首页 > 代码库 > [NOI1999]内存分配解题报告

[NOI1999]内存分配解题报告

2024-10-30 22:53:39 216人阅读

[NOI1999] 内存分配

时间限制：1 s 内存限制：128 MB

内存是计算机重要的资源之一，程序运行的过程中必须对内存进行分配。

经典的内存分配过程是这样进行的：

内存以内存单元为基本单位，每个内存单元用一个固定的整数作为标识，称为地址。地址从0开始连续排列，地址相邻的内存单元被认为是逻辑上连续的。我们把从地址i开始的s个连续的内存单元称为首地址为i长度为s的地址片。
运行过程中有若干进程需要占用内存，对于每个进程有一个申请时刻T，需要内存单元数M及运行时间P。在运行时间P内（即T时刻开始，T+P时刻结束），这M个被占用的内存单元不能再被其他进程使用。
假设在T时刻有一个进程申请M个单元，且运行时间为P，则：
1. 若T时刻内存中存在长度为M的空闲地址片，则系统将这M个空闲单元分配给该进程。若存在多个长度为M个空闲地址片，则系统将首地址最小的那个空闲地址片分配给该进程。
2. 如果T时刻不存在长度为M的空闲地址片，则该进程被放入一个等待队列。对于处于等待队列队头的进程，只要在任一时刻，存在长度为M的空闲地址片，系统马上将该进程取出队列，并为它分配内存单元。注意，在进行内存分配处理过程中，处于等待队列队头的进程的处理优先级最高，队列中的其它进程不能先于队头进程被处理。

现在给出一系列描述进程的数据，请编写一程序模拟系统分配内存的过程。

输入

第一行是一个数N，表示总内存单元数（即地址范围从0到N-1）
从第二行开始每行描述一个进程的三个整数T、M、P（M<=N）。
数据已按T从小到大排序。
最后一行用三个0表示结束。
输入文件最多10000行，且所有数据都小于10^9。
输入文件中同一行相邻两项之间用一个或多个空格隔开。

输出

包括2行。
第一行是全部进程都运行完毕的时刻。
第二行是被放入过等待队列的进程总数。

样例输入

样例输出

12
2

样例示例

时

刻

内存占用情况

进程事件

进程A申请空间（M=3,P=10）<成功>

进程B申请空间（M=4,P=3）<成功>

进程C申请空间（M=4,P=4）<失败进入等待队列>

进程D申请空间（M=1,P=4）<成功>

进程B结束，释放空间

进程C从等待队列取出，分配空间

进程E申请空间（M=3,P=4）<失败进入等待队列>

进程D结束，释放空间

进程E从等待队列取出，分配空间

进程C结束，释放空间

进程A结束，释放空间

进程E结束，释放空间

这道题应该说给我很大收获。

一、线段树

起初我本想用线段树解决这个问题，但没有注意到题中所说所有数据小于10^9,于是RE了两个点。①以后一定要认真读数据范围！

后来。。（由于COGS给的标签——动态开点——的原因。。）我想到可以不需要把整棵树建出来，只需要把询问的节点建出来就可以了，这样的话，若设任务申请数为M，则空间复杂度可以达到技术分享，时间复杂度可以达到.

但是由于没有写过，所以写起来蛋疼了好久。。但是也算有收获，即：

②为了降低空间复杂度，可以不用把整棵线段树都建出来。

二、堆

在处理结束时间的时候脑残了用了set，其实完全没必要。。就像刚刚做的派遣一样，空增加了代码量！

注意到其实我们只是每次取出时间最早的，使用堆其实完全就可以了。

⑤这也给我在使用数据结构中的一些启示，在使用数据结构时，一定要弄清自己需要做什么，需要用什么，选择恰当的数据结构；平衡树当然可以完成堆的功能，但很多时候，我们并不需要花费如此大的代码代价。

在这过程中，也有些收获；以前一直不太会写up操作，现在总算弄明白了，③在up的过程中应该把两个兄弟中较小的一个换到根上去。

三、链表

我们当然可以用链表来处理这个问题，用链表来表示间断的可行区间，然后从左往右找第一个合法的；并同样地用堆维护结束时间。

但是显然这样做的时间复杂度高达技术分享，但是为什么不仅能A，还比上面的线段树做法还快呢。

首先我们注意到，技术分享的O时间复杂度远大于T，实际上最差情况也不会超过10^6~7，再加上其常数小，数据弱。。

④当算出一个10^8的时间复杂度时，完全没有必要心灰意冷，如果发现常数小的话是完全没问题的，而且，这个常数，并不是指的代码复杂度，而是实际过程中的运算次数，如本题的时间复杂度就是一个相当经典的例子；10^8也许就是正解！

线段树+平衡树：

#include<iostream>
using namespace std;
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define root 0,0,N
struct TS{
	int max,lmax,rmax,lR,rL,lazy;
}tree[4000000];
int tot=2,lson[4000000],rson[4000000];
char * ptr=(char *)malloc(500000);
inline void in(int &x){
	while(*ptr<'0'||*ptr>'9')++ptr;
	x=0;
	while(*ptr>47&&*ptr<58)x=x*10+*ptr++-'0';
}
inline void in(long long &x){
	while(*ptr<'0'||*ptr>'9')++ptr;
	x=0;
	while(*ptr>47&&*ptr<58)x=x*10+*ptr++-'0';
}
struct SS{
	long long time;
	int l,r;
	inline bool operator < (const SS a) const{
		return time<a.time;
	}
};
inline int newnode(int l,int r,int flag){
	if(flag)tree[tot]=(TS){r-l+1,r-l+1,r-l+1,r,l,-1};
	else tree[tot]=(TS){0,0,0,l-1,r+1,-1};
	return tot++;
}
inline void extend(int node,int l,int r){
	if(!lson[node]){
		lson[node]=newnode(l,(l+r)>>1,tree[node].max);
		rson[node]=newnode(((l+r)>>1)+1,r,tree[node].max);
	}
}
inline void paint(int node,int l,int r,int flag){
	if(flag)tree[node]=(TS){r-l+1,r-l+1,r-l+1,r,l,1};
	else tree[node]=(TS){0,0,0,l-1,r+1,0};
}
inline void pushdown(int node,int l,int r){
	if(tree[node].lazy+1){
		paint(lson[node],l,(l+r)>>1,tree[node].lazy);
		paint(rson[node],((l+r)>>1)+1,r,tree[node].lazy);
		tree[node].lazy=-1;
	}
}
inline void update(int node,int l,int r,int a,int b,int x){
	if(l>b||r<a)return;
	if(a<=l&&r<=b){
		paint(node,l,r,x);
		return;
	}
	extend(node,l,r);
	pushdown(node,l,r);
	update(lson[node],l,(l+r)>>1,a,b,x);
	update(rson[node],((l+r)>>1)+1,r,a,b,x);
	
	tree[node].lmax=tree[lson[node]].lmax;
	if(tree[lson[node]].lmax==(l+r>>1)-l+1){
		tree[node].lmax+=tree[rson[node]].lmax;
		tree[node].lR=tree[rson[node]].lR;
	}
	else tree[node].lR=tree[lson[node]].lR;
	
	tree[node].rmax=tree[rson[node]].rmax;
	if(tree[rson[node]].rmax==r-(l+r>>1)){
		tree[node].rmax+=tree[lson[node]].rmax;
		tree[node].rL=tree[lson[node]].rL;
	}
	else tree[node].rL=tree[rson[node]].rL;
	
	tree[node].max=max(tree[lson[node]].max,max(tree[rson[node]].max,tree[lson[node]].rmax+tree[rson[node]].lmax));
	
	//printf("U:[%d,%d]:%d %d %d\n",l,r,tree[node].lmax,tree[node].max,tree[node].rmax);
}
inline int find(int node,int l,int r,int len){
	//printf("F:[%d,%d]:%d %d %d---%d\n",l,r,tree[node].lmax,tree[node].max,tree[node].rmax,len);
	if(l==r)return l;
	extend(node,l,r);
	pushdown(node,l,r);
	if(tree[lson[node]].max>=len)return find(lson[node],l,(l+r)>>1,len);
	if(tree[lson[node]].rmax+tree[rson[node]].lmax>=len)return tree[lson[node]].rL;
	return find(rson[node],((l+r)>>1)+1,r,len);
}
#include<set>
#define MAXT 0x7fffffffffffffff
int main(){
	freopen("memory.in","r",stdin);
	freopen("memory.out","w",stdout);
	/*--Read----*/
	fread(ptr,1,500000,stdin);
	
	int N;
	in(N);
	
	int tot=0;
	struct OS{
		long long T;
		int M,P;
	}oq[10000];
	
	in(oq[0].T),in(oq[0].M),in(oq[0].P);
	while(oq[tot].T||oq[tot].M||oq[tot].P)in(oq[++tot].T),in(oq[tot].M),in(oq[tot].P);
	/*----Pre-work---*/
	if(!tot){
		printf("0\n0");
		return 0;
	}
	
	tree[1]=(TS){N,N,N,N,0,-1};
	--N;
	
	int h=0,t=0,x=0,L;
	
	multiset<SS> over;
	over.insert((SS){MAXT,0,0});
	
	oq[tot].T=MAXT;
	
	struct QS{
		int M,P;
	}q[10000];
	
	long long time=-1,lastT;
	/*----Work----*/
	while(time!=MAXT){
		//printf("---- %I64d:%d-------\n",time,t);
		/*----pop----*/
		for(;over.begin()->time==time;over.erase(over.begin()))update(1,0,N,over.begin()->l,over.begin()->r,1);
		/*--push the task in the q--*/
		for(;h<t&&q[h].M<=tree[1].max;++h){
			L=find(1,0,N,q[h].M);
			update(1,0,N,L,L+q[h].M-1,0);
			over.insert((SS){time+q[h].P,L,L+q[h].M-1});
			//cout<<"push(q):"<<L<<","<<L+q[h].M-1<<"-----"<<time+q[h].P<<"\n";
		}
		/*--push the task in the oq--*/
		for(;oq[x].T==time;++x)
			if(oq[x].M>tree[1].max)q[t++]=(QS){oq[x].M,oq[x].P};
			else{
				L=find(1,0,N,oq[x].M);
				update(1,0,N,L,L+oq[x].M-1,0);
				over.insert((SS){time+oq[x].P,L,L+oq[x].M-1});
				//cout<<"push(oq):"<<L<<","<<L+oq[x].M-1<<"-----"<<time+oq[x].P<<"\n";
			}
		/*--to next time--*/
		lastT=time;
		time=min(over.begin()->time,oq[x].T);
	}
	cout<<lastT<<"\n"<<t;
}

线段树+堆：

#include<iostream>
using namespace std;
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define root 0,0,N
struct TS{
	int max,lmax,rmax,lR,rL,lazy;
}tree[4000000];
int tot=2,lson[4000000],rson[4000000];
char * ptr=(char *)malloc(500000);
inline void in(int &x){
	while(*ptr<'0'||*ptr>'9')++ptr;
	x=0;
	while(*ptr>47&&*ptr<58)x=x*10+*ptr++-'0';
}
inline void in(long long &x){
	while(*ptr<'0'||*ptr>'9')++ptr;
	x=0;
	while(*ptr>47&&*ptr<58)x=x*10+*ptr++-'0';
}
inline int newnode(int l,int r,int flag){
	if(flag)tree[tot]=(TS){r-l+1,r-l+1,r-l+1,r,l,-1};
	else tree[tot]=(TS){0,0,0,l-1,r+1,-1};
	return tot++;
}
inline void extend(int node,int l,int r){
	if(!lson[node]){
		lson[node]=newnode(l,(l+r)>>1,tree[node].max);
		rson[node]=newnode(((l+r)>>1)+1,r,tree[node].max);
	}
}
inline void paint(int node,int l,int r,int flag){
	if(flag)tree[node]=(TS){r-l+1,r-l+1,r-l+1,r,l,1};
	else tree[node]=(TS){0,0,0,l-1,r+1,0};
}
inline void pushdown(int node,int l,int r){
	if(tree[node].lazy+1){
		paint(lson[node],l,(l+r)>>1,tree[node].lazy);
		paint(rson[node],((l+r)>>1)+1,r,tree[node].lazy);
		tree[node].lazy=-1;
	}
}
inline void update(int node,int l,int r,int a,int b,int x){
	if(l>b||r<a)return;
	if(a<=l&&r<=b){
		paint(node,l,r,x);
		return;
	}
	extend(node,l,r);
	pushdown(node,l,r);
	update(lson[node],l,(l+r)>>1,a,b,x);
	update(rson[node],((l+r)>>1)+1,r,a,b,x);
	
	tree[node].lmax=tree[lson[node]].lmax;
	if(tree[lson[node]].lmax==(l+r>>1)-l+1){
		tree[node].lmax+=tree[rson[node]].lmax;
		tree[node].lR=tree[rson[node]].lR;
	}
	else tree[node].lR=tree[lson[node]].lR;
	
	tree[node].rmax=tree[rson[node]].rmax;
	if(tree[rson[node]].rmax==r-(l+r>>1)){
		tree[node].rmax+=tree[lson[node]].rmax;
		tree[node].rL=tree[lson[node]].rL;
	}
	else tree[node].rL=tree[rson[node]].rL;
	
	tree[node].max=max(tree[lson[node]].max,max(tree[rson[node]].max,tree[lson[node]].rmax+tree[rson[node]].lmax));
	
	//printf("U:[%d,%d]:%d %d %d\n",l,r,tree[node].lmax,tree[node].max,tree[node].rmax);
}
inline int find(int node,int l,int r,int len){
	//printf("F:[%d,%d]:%d %d %d---%d\n",l,r,tree[node].lmax,tree[node].max,tree[node].rmax,len);
	if(l==r)return l;
	extend(node,l,r);
	pushdown(node,l,r);
	if(tree[lson[node]].max>=len)return find(lson[node],l,(l+r)>>1,len);
	if(tree[lson[node]].rmax+tree[rson[node]].lmax>=len)return tree[lson[node]].rL;
	return find(rson[node],((l+r)>>1)+1,r,len);
}
#include<set>
#define MAXT 0x7fffffffffffffff
struct SS{
	long long time;
	int l,r;
	inline bool operator < (const SS a) const{
		return time<a.time;
	}
}heap[10000];
int heapsize=2;
inline void up(int now){
	int next=now>>1;
	while(next){
		if((now^1)<heapsize&&heap[now^1]<heap[now])now^=1;
		if(heap[next]<heap[now])return;
		swap(heap[next],heap[now]);
		now=next,next>>=1;
	}
}
inline void down(int now){
	int next=now<<1;
	while(next<heapsize){
		if(next+1<heapsize&&heap[next+1]<heap[next])++next;
		if(heap[now]<heap[next])return;
		swap(heap[now],heap[next]);
		now=next,next<<=1;
	}
}
int main(){
	freopen("memory.in","r",stdin);
	freopen("memory.out","w",stdout);
	/*--Read----*/
	fread(ptr,1,500000,stdin);
	
	int N;
	in(N);
	
	int tot=0;
	struct OS{
		long long T;
		int M,P;
	}oq[10000];
	
	in(oq[0].T),in(oq[0].M),in(oq[0].P);
	while(oq[tot].T||oq[tot].M||oq[tot].P)in(oq[++tot].T),in(oq[tot].M),in(oq[tot].P);
	/*----Pre-work---*/
	if(!tot){
		printf("0\n0");
		return 0;
	}
	
	tree[1]=(TS){N,N,N,N,0,-1};
	--N;
	
	int h=0,t=0,x=0,L;
	
	oq[tot].T=MAXT;
	
	struct QS{
		int M,P;
	}q[10000];
	
	long long time=-1,lastT;
	
	heap[1]=(SS){MAXT,0,0};
	/*----Work----*/
	while(time!=MAXT){
		/*----pop----*/
		while(heap[1].time==time){
			update(1,0,N,heap[1].l,heap[1].r,1);
			heap[1]=heap[--heapsize];
			down(1);
		}
		/*--push the task in the q--*/
		for(;h<t&&q[h].M<=tree[1].max;++h){
			L=find(1,0,N,q[h].M);
			update(1,0,N,L,L+q[h].M-1,0);
			heap[heapsize]=(SS){time+q[h].P,L,L+q[h].M-1};
			up(heapsize++);
			//cout<<"push(q):"<<L<<","<<L+q[h].M-1<<"-----"<<time+q[h].P<<"\n";
		}
		/*--push the task in the oq--*/
		for(;oq[x].T==time;++x)
			if(oq[x].M>tree[1].max)q[t++]=(QS){oq[x].M,oq[x].P};
			else{
				L=find(1,0,N,oq[x].M);
				update(1,0,N,L,L+oq[x].M-1,0);
				heap[heapsize]=(SS){time+oq[x].P,L,L+oq[x].M-1};
				up(heapsize++);
				//cout<<"push(oq):"<<L<<","<<L+oq[x].M-1<<"-----"<<time+oq[x].P<<"\n";
			}
		/*--to next time--*/
		lastT=time;
		time=min(heap[1].time,oq[x].T);
	}
	cout<<lastT<<"\n"<<t;
}

链表+堆：

#include<iostream>
using namespace std;
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
char * ptr=(char *)malloc(5000000);
inline void in(int &x){
	while(*ptr<'0'||*ptr>'9')++ptr;
	x=0;
	while(*ptr>47&&*ptr<58)x=x*10+*ptr++-'0';
}
inline void in(long long &x){
	while(*ptr<'0'||*ptr>'9')++ptr;
	x=0;
	while(*ptr>47&&*ptr<58)x=x*10+*ptr++-'0';
}
struct LS{
	LS * next;
	int l,r;
};
struct HS{
	long long time;
	int l,r;
	inline bool operator < (const HS a) const{
		return time<a.time;
	}
}heap[10000];
int heapsize=2;
inline void down(int now){
	int next=now<<1;
	while(next<heapsize){
		if(next+1<heapsize&&heap[next+1]<heap[next])++next;
		if(heap[now]<heap[next])return;
		swap(heap[now],heap[next]);
		now=next,next<<=1;
	}
}
inline void up(int now){
	int next=now>>1;
	while(next){
		if((now^1)<heapsize&&heap[now^1]<heap[now])now^=1;
		if(heap[next]<heap[now])return;
		swap(heap[next],heap[now]);
		now=next,next>>=1;
	}
}
#define MAXT 0x7fffffffffffffff
int main(){
	/*----Read----*/
	freopen("memory.in","r",stdin);
	freopen("memory.out","w",stdout);
	fread(ptr,1,5000000,stdin);
	int N,tot=0;
	in(N);
	struct OS{
		long long T;
		int M,P;
	}oq[10000];
	in(oq[0].T),in(oq[0].M),in(oq[0].P);
	while(oq[tot].T||oq[tot].M||oq[tot].P)in(oq[++tot].T),in(oq[tot].M),in(oq[tot].P);
	oq[tot].T=MAXT;
	/*-----Pre-work----*/
	LS *head=new LS((LS){0,-1,-2}),*I,*Ipred;
	head->next=new LS((LS){0,0,N-1});
	head->next->next=new LS((LS){0,N+1,N});
	
	struct QS{
		int M,P;
	}q[10000];
	int h=0,t=0,x=0;
	
	heap[1]=(HS){MAXT,0,0};
	
	long long time=-1,lastT;
	/*---Work------*/
	if(!tot){
		printf("0\n0");
		return 0;
	}
	
	while(time!=MAXT){
		//cout<<"-----"<<time<<"-----\n";
		while(time==heap[1].time){
			I=head;
			while(I->next->r<heap[1].l){
				Ipred=I;
				I=I->next;
			}
			
			I->next=new LS((LS){I->next,heap[1].l,heap[1].r});
			if(I->r==heap[1].l-1){
				Ipred->next=I->next;
				I->next->l=I->l;
			}
			if(I->next->next->l==heap[1].r+1){
				I->next->r=I->next->next->r;
				I->next->next=I->next->next->next;
			}
			
			//cout<<"Pop:"<<heap[1].l<<" "<<heap[1].r<<endl;
			heap[1]=heap[--heapsize];
			down(1);
		}
		for(;h<t;++h){
			I=head;
			while(I->next&&I->r-I->l+1<q[h].M){
				Ipred=I;
				I=I->next;
			}
			if(I->next){
				heap[heapsize]=(HS){time+q[h].P,I->l,I->l+q[h].M-1};
				up(heapsize++);
				//cout<<"qPush:"<<I->l<<" "<<I->l+q[h].M-1<<endl;
				if(I->r-I->l+1==q[h].M)Ipred->next=I->next;
				else I->l+=q[h].M;
			}
			else break;
		}
		for(;oq[x].T==time;++x){
			I=head;
			while(I->next&&I->r-I->l+1<oq[x].M){
				Ipred=I;
				I=I->next;
				//cout<<"FS:"<<I->l<<","<<I->r<<endl;
			}
			if(I->next){
				heap[heapsize]=(HS){time+oq[x].P,I->l,I->l+oq[x].M-1};
				up(heapsize++);
				//cout<<"oqPush:"<<I->l<<" "<<I->l+oq[x].M-1<<endl;
				if(I->r-I->l+1==oq[x].M)Ipred->next=I->next;
				else I->l+=oq[x].M;
			}
			else q[t++]=(QS){oq[x].M,oq[x].P};
		}
		lastT=time;
		time=min(heap[1].time,oq[x].T);
	}
	cout<<lastT<<"\n"<<t;
}

[NOI1999]内存分配解题报告

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > [NOI1999]内存分配 解题报告