首页 > 代码库 > [NOI1999]内存分配 解题报告
[NOI1999]内存分配 解题报告
[NOI1999] 内存分配
时间限制:1 s 内存限制:128 MB- 内存以内存单元为基本单位,每个内存单元用一个固定的整数作为标识,称为地址。地址从0开始连续排列,地址相邻的内存单元被认为是逻辑上连续的。我们把从地址i开始的s个连续的内存单元称为首地址为i长度为s的地址片。
- 运行过程中有若干进程需要占用内存,对于每个进程有一个申请时刻T,需要内存单元数M及运行时间P。在运行时间P内(即T时刻开始,T+P时刻结束),这M个被占用的内存单元不能再被其他进程使用。
- 假设在T时刻有一个进程申请M个单元,且运行时间为P,则:
- 若T时刻内存中存在长度为M的空闲地址片,则系统将这M个空闲单元分配给该进程。若存在多个长度为M个空闲地址片,则系统将首地址最小的那个空闲地址片分配给该进程。
- 如果T时刻不存在长度为M的空闲地址片,则该进程被放入一个等待队列。对于处于等待队列队头的进程,只要在任一时刻,存在长度为M的空 闲地址片,系统马上将该进程取出队列,并为它分配内存单元。注意,在进行内存分配处理过程中,处于等待队列队头的进程的处理优先级最高,队列中的其它进程 不能先于队头进程被处理。
- 第一行是一个数N,表示总内存单元数(即地址范围从0到N-1)
- 从第二行开始每行描述一个进程的三个整数T、M、P(M<=N)。
- 数据已按T从小到大排序。
- 最后一行用三个0表示结束。
- 输入文件最多10000行,且所有数据都小于10^9。
- 输入文件中同一行相邻两项之间用一个或多个空格隔开。
- 包括2行。
- 第一行是全部进程都运行完毕的时刻。
- 第二行是被放入过等待队列的进程总数。
内存是计算机重要的资源之一,程序运行的过程中必须对内存进行分配。
经典的内存分配过程是这样进行的:
现在给出一系列描述进程的数据,请编写一程序模拟系统分配内存的过程。
输入
输出
样例输入
10 1 3 10 2 4 3 3 4 4 4 1 4 5 3 4 0 0 0
样例输出
12 2
样例示例
时 刻 T | 内存占用情况 | 进程事件 | |||||||||||
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 进程A申请空间(M=3,P=10)<成功> | |||
1 | A |
|
|
|
|
|
|
| |||||
2 | A | B |
|
|
| 进程B申请空间(M=4,P=3)<成功> | |||||||
3 | A | B |
|
|
| 进程C申请空间(M=4,P=4)<失败进入等待队列> | |||||||
4 | A | B | D |
|
| 进程D申请空间(M=1,P=4)<成功> | |||||||
5 | A | C | D |
|
| 进程B结束,释放空间 进程C从等待队列取出,分配空间 进程E申请空间(M=3,P=4)<失败进入等待队列> | |||||||
6 | A | C | D |
|
|
| |||||||
7 | A | C | D |
|
|
| |||||||
8 | A | C | E | 进程D结束,释放空间 进程E从等待队列取出,分配空间 | |||||||||
9 | A |
|
|
|
| E | 进程C结束,释放空间 | ||||||
10 | A |
|
|
|
| E |
| ||||||
11 |
|
|
|
|
|
|
| E | 进程A结束,释放空间 | ||||
12 |
|
|
|
|
|
|
|
|
|
| 进程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]内存分配 解题报告