1193.cpp

acm-pku-1193 内存分配 北大acm解题代码

#include<iostream>

using namespace std;

int cLen,cTime;

struct waitlist
{
	int usetime;
	int usemem;
	waitlist * next;
}*whead,*wend;

struct uselist
{
	int keeptime;
	int memstar;
	int keepmem;
	uselist * next;
}*uhead;

struct freelist
{
	int start;
	int Len;
	freelist * next;
}*fhead;

void wInsort(waitlist * tp)
{
	if(whead->next==NULL)  wend=whead;
	tp->next=NULL;
	wend->next=tp;
	wend=tp;
}

void uInsort(uselist * tp)
{
	uselist *p; p=uhead;
	while(p->next) 
	{
		if(p->next->keeptime<tp->keeptime) p=p->next;
		else break;
	}
	tp->next=p->next;
	p->next=tp;
}

void fInsort(freelist * tp)
{
	freelist *p; p=fhead;
	while(p->next) 
	{
		if(p->next->start<tp->start) p=p->next;
		else break;
	}
	tp->next=p->next;
	p->next=tp;
}

int Getmem(int L)
{
	int mstart;
	freelist *p,*temp; p=fhead;

	while(p->next)
	{
		if(L>p->next->Len) p=p->next;
		else break;
	}

	if(p->next==NULL) return -1;
	mstart=p->next->start;
	if(L<p->next->Len)
	{
		temp=new freelist;
	    temp->start=p->next->start+L;
		temp->Len=p->next->Len-L;
		p->next=p->next->next;
		fInsort(temp); 
	}
	else p->next=p->next->next;
	return mstart;
}

void getwaitlist(int t)
{
	uselist * up;
	while(whead->next)
	{
		up=new uselist;
		if((up->memstar=Getmem(whead->next->usemem))>=0) 
		{
			up->keepmem=whead->next->usemem;
			up->keeptime=t+whead->next->usetime;
			uInsort(up);
			whead->next=whead->next->next;
		}
		else break;
	}
}

void Freemem(int mstar,int mLen)
{ 
	freelist *p,*temp; p=fhead;
	while(p->next) 
	{
		if(p->next->start<mstar) p=p->next;
		else break;
	}

	if(p==fhead)
	{

		if(p->next&&mstar+mLen==p->next->start)
		{
			p->next->start=mstar;
			p->next->Len=mLen+p->next->Len;
		}
		else 
		{
			temp=new freelist; temp->Len=mLen;
			temp->start=mstar; fInsort(temp);
		}
	}
	else if(p->start+p->Len==mstar&&p->next&&mstar+mLen==p->next->start) 
	{
		p->Len=p->Len+p->next->Len+mLen;
		p->next=p->next->next;
	}
	else if(p->start+p->Len==mstar)
	{
		p->Len=p->Len+mLen;
	}
	else if(p->next&&mstar+mLen==p->next->start)
	{
		
		temp=new freelist;      temp->Len=mLen+p->next->Len;
		p->next=p->next->next;  temp->start=mstar;
		fInsort(temp);
	}
	else
	{
		temp=new freelist; temp->Len=mLen;  
		temp->start=mstar; fInsort(temp);
	}
}

int main(void)
{
	int n,t,m,p,b;

   while(cin>>n)
 {
	uselist *up; waitlist *wp;
	fhead=new freelist; uhead=new uselist; whead=new waitlist;
	cLen=0;
	fhead->Len=n;
	fhead->next=new freelist; fhead->next->Len=n;
	fhead->next->start=0;           fhead->next->next=NULL;
	uhead->next=NULL;         
	wend=whead;                     whead->next=NULL;

	while(1)
	{
		cin>>t>>m>>p;
		if(t==m&&m==p&&p==0) break;

		while(uhead->next&&t>=uhead->next->keeptime)
		{
			b=uhead->next->keeptime;
			while(uhead->next&&uhead->next->keeptime==b)
			{
				Freemem(uhead->next->memstar,uhead->next->keepmem);
				uhead->next=uhead->next->next;
			}
			getwaitlist(b);
		}

		up=new uselist;
		if((up->memstar=Getmem(m))>=0)
		{
			up->keepmem=m;
			up->keeptime=t+p;
		    uInsort(up);
		}
		else 
		{
			wp=new waitlist; 
			wp->usemem=m;   wp->usetime=p;
		    wInsort(wp);    cLen++;
		}
	
	}
	while(whead->next)
	{
		up=new uselist;
		if((up->memstar=Getmem(whead->next->usemem))>=0)
		{
			up->keepmem=whead->next->usemem;
			up->keeptime=b+whead->next->usetime;
			uInsort(up);
			whead=whead->next;
		}
		else
		{
			b=uhead->next->keeptime;
			while(uhead->next&&b==uhead->next->keeptime)
			{
				Freemem(uhead->next->memstar,uhead->next->keepmem);
			    uhead->next=uhead->next->next;
			}
		}
	}
	while(uhead->next) uhead=uhead->next;
	cTime=uhead->keeptime;

	cout<<cTime<<endl<<cLen<<endl;
   }
	return 0;
}