schedule.cpp

acm亚洲区竞赛的一个题目（关于任务调度的）以及我的程序实现Asia Regional_Taipei Site Dec.10-13.1999Program EBroadcast Scheduling

#include"Schedule.h"
#include<iostream.h>
#include<fstream.h>
#include<iomanip.h>
//========================================================
Schedule::Schedule()
{
	this->m_bEnd=false;
	this->m_nRequestNum=0;
	this->m_nSongNum=0;

	this->m_giFcfs.currentTime=0;
	this->m_giFcfs.totalWait=0;
	this->m_giBest.currentTime=0;
	this->m_giBest.totalWait=0;

}
//=========================================================
void Schedule::ReadDescriptionSection(ifstream & infile)
{
	int index,length;
	for(int i=0;;i++)
	{
		infile>>index;
		if(-1==index)break;
		if(i<200)this->m_liLengthArray[i].index=index;
		
		infile>>length;
		if(i<200)this->m_liLengthArray[i].length=length;
	}
	this->m_nSongNum=i;
}
//========================================================
int Schedule::GetInteger(ifstream & infile)
{
	char zero='0';
	char ch1,ch2;
	infile>>ch1>>ch2;
	int n=(int(ch1-zero))*10 + int(ch2-zero);
	return n;
}
//========================================================
void Schedule::ReadRequestSection(ifstream & infile)
{
	int index,hour,minute;
	char ch;
	int time;

    for(int i=0;;i++)
	{
		infile>>index;
		if(index==0)
		{
			this->m_bEnd=true;
			break;
		}
		else if(index==-1)
			break;

		this->m_siSongArray[i].index=index;
/////////////////////////////////////////////////////////
		//infile>>hour>>ch>>minute;
		hour=GetInteger(infile);
		infile>>ch;
		minute=GetInteger(infile);
///////////////////////////////////////////////////////////
		time=hour*60+minute;
		this->m_siSongArray[i].start=time;
		this->m_siSongArray[i].length=this->GetSongLength(index);
	}
	this->m_nRequestNum=i;
}
//=============================================================
int Schedule::GetSongLength(int index)
{
	for(int i=0;i<this->m_nSongNum;i++)
		if(this->m_liLengthArray[i].index==index)
			return this->m_liLengthArray[i].length;
	return 0;
}
//==============================================================
void Schedule::Run(ifstream & infile)
{
	this->ReadDescriptionSection(infile);
	while(!this->m_bEnd)
	{
	  this->Clean();
      this->ReadRequestSection(infile);	  
	  this->SortRequests();
	  if(!this->CanSchedule())
		  continue;
	  this->FindBestScheduling();//////////////////////////
	}
}
//==============================================================
void Schedule::Swap(SongInfo & a,SongInfo & b)
{	
	SongInfo temp=a;
	a=b;
	b=temp;
}
//==============================================================
void Schedule::SortRequests()
{
    for(int i=0;i<this->m_nRequestNum-1;i++)
		for(int j=this->m_nRequestNum-1;j>i;j--)
			if(this->m_siSongArray[j].start
				< this->m_siSongArray[j-1].start)
			{
              Swap(m_siSongArray[j],m_siSongArray[j-1]);
              
			}


}
//===============================================================
bool Schedule::CanSchedule()
{
	for(int i=0;i<this->m_nRequestNum;i++)
	{
		this->m_siFcfsSchedule[i].index=this->m_siSongArray[i].index;
		if(this->m_siSongArray[i].start>=this->m_giFcfs.currentTime)
		{
			this->m_giFcfs.currentTime
			=this->m_siSongArray[i].start+this->m_siSongArray[i].length;
			
			this->m_siFcfsSchedule[i].actualStart
			=this->m_siSongArray[i].start;

			this->m_siFcfsSchedule[i].wait=0;
		}
		else
		{
					
			this->m_siFcfsSchedule[i].actualStart
			=this->m_giFcfs.currentTime;

			this->m_siFcfsSchedule[i].wait
				=this->m_siFcfsSchedule[i].actualStart
				  -this->m_siSongArray[i].start;

			this->m_giFcfs.currentTime +=m_siSongArray[i].length;
			this->m_giFcfs.totalWait +=m_siFcfsSchedule[i].wait;
		}
	}

	if(m_giFcfs.currentTime<=24*60)
	{
		//USED FOR TEST ONLY!!!
		//*******************************
		/*
		cout<<this->m_nRequestNum<<" requests have been successfully scheduled.\n";
	    cout.precision(3);
		cout<<"The average waiting time is "<<double(this->m_giFcfs.totalWait)/this->m_nRequestNum
		   <<" minute(s).\n";
	   for(int i=0;i<this->m_nRequestNum;i++)
	   {
		   int t=this->m_siFcfsSchedule[i].actualStart;
		   int minute=t/60;
		   int second=t%60;

		   if(minute<10)
		      cout<<0;	   
		   cout<<minute<<":";

           if(second<10)
		      cout<<0;	 
		   cout<<second;

		   cout<<"  "<<this->m_siFcfsSchedule[i].index<<endl;
	   }
	   cout<<endl;
	   */
       //*********************************
      
	    
		return true;
	}
	else
	{
		cout<<"no solution exists\n\n";
		return false;
	}
}
//=============================================================
void Schedule::Clean()
{
	this->m_bEnd=false;
	this->m_nRequestNum=0;
	////////////////////this->m_nSongNum=0;

	this->m_giFcfs.currentTime=0;
	this->m_giFcfs.totalWait=0;
	this->m_giBest.currentTime=0;
	this->m_giBest.totalWait=0;
}
//==============================================================
void Schedule::FindBestScheduling()
{
	//for(int q=0;q<this->m_nRequestNum;q++)
	//	cout<<this->m_siSongArray[q].index<<"  "<<m_siSongArray[q].length
	//	<<"     "<<this->m_siSongArray[q].start<<endl;

		//for(int k=0;k<this->m_nRequestNum;k++)
		//cout<<this->m_siSongArray[k].index<<"    "
		//<<this->m_siSongArray[k].start<<"    "
		//<<this->m_siSongArray[k].length<<endl;

	for(int i=0;i<this->m_nRequestNum;i++)
   {
	   
	   this->m_siBestSchedule[i].index=this->m_siSongArray[i].index;
	   }
   for(i=0;i<this->m_nRequestNum;i++)
   {
	   
	   //this->m_siBestSchedule[i].index=this->m_siSongArray[i].index;
	   if(this->m_siSongArray[i].start>=this->m_giBest.currentTime)
	   {
		   this->m_giBest.currentTime=this->m_siSongArray[i].start+this->m_siSongArray[i].length;
		   this->m_siBestSchedule[i].actualStart=this->m_siSongArray[i].start;
		   this->m_siBestSchedule[i].wait=0;
	   }
	   else
	   {
             //find the position of j
             for(int j=i-1;j>=0;j--)
		      if(this->m_siBestSchedule[j].actualStart<=this->m_siSongArray[i].start)
				  break;
	
            //suppose fcfs is the best method
	        int bestPos=i;
//////////////////////////////////////////////////
			int minWaitSum=this->m_giBest.currentTime-this->m_siSongArray[i].start;
			//insert before j
			int dWait=this->m_siSongArray[i].length+this->m_siSongArray[i].start
				       -this->m_siBestSchedule[j].actualStart;
		
             int waitSum=(i-j)*dWait;
            //compare "fcfs" and "insert before j"
	
			if(waitSum<minWaitSum)//insert before j is better
			{
				minWaitSum=waitSum;
				bestPos=j;

				this->m_siBestSchedule[i].wait=0;
				this->m_siBestSchedule[i].actualStart=this->m_siSongArray[i].start;
			 
			}
			else//fcfs is better
			{
				this->m_siBestSchedule[i].wait=this->m_giBest.currentTime-this->m_siSongArray[i].start;
				this->m_siBestSchedule[i].actualStart=this->m_giBest.currentTime;
			   
			}
          
         for(int k=j+1;k<i;k++)
		 {
			
			 waitSum=(i-k)*m_siSongArray[i].length
				 + m_siBestSchedule[k].actualStart - m_siSongArray[i].start;
			 
			 if(waitSum<minWaitSum)
			 {
				 minWaitSum=waitSum;
				 bestPos=k;

				 this->m_siBestSchedule[i].wait=this->m_siBestSchedule[k].actualStart
					     -this->m_siSongArray[i].start;
				 this->m_siBestSchedule[i].actualStart=this->m_siBestSchedule[k].actualStart;
			     
			 }
		 }//end of for
            		 
		 int dt=0;///////////
		 
		 if(bestPos==i)//fcfs
		 {}
		 else if(bestPos==j)
		 {
			 dt=m_siSongArray[i].start
				     - m_siBestSchedule[j].actualStart;////////////////
			 for(int k=j;k<i;k++)
			 {
				 int t=this->m_siSongArray[i].length+this->m_siSongArray[i].start
					    -this->m_siBestSchedule[j].actualStart;

				 this->m_siBestSchedule[k].actualStart+=t;
                 this->m_siBestSchedule[k].wait+=t;
			 }
		 }
		 else
		 {
			 for(int k=bestPos;k<i;k++)
			 {
				 int t=this->m_siSongArray[i].length;
				 this->m_siBestSchedule[k].actualStart+=t;
				 this->m_siBestSchedule[k].wait+=t;
			 }
		 }
	     
		 //do the actual insert
		 this->m_giBest.currentTime += dt+this->m_siSongArray[i].length;////////
		 this->m_giBest.totalWait+=minWaitSum;

		 ScheduleInfo temp=this->m_siBestSchedule[i];
		 for(int m=i-1;m>=bestPos;m--)
		 {
			this->m_siBestSchedule[m+1]=this->m_siBestSchedule[m];
		 }
		 this->m_siBestSchedule[bestPos]=temp;

	   }//end of outer else
   }//end of outer for

   if(this->m_giBest.currentTime<=24*60)
   {
	   cout<<this->m_nRequestNum<<" requests have been successfully scheduled.\n";
	   cout.precision(3);
	   cout<<"The average waiting time is "<<double(m_giBest.totalWait)/m_nRequestNum
		   <<" minute(s).\n";
	   for(int i=0;i<this->m_nRequestNum;i++)
	   {
		    int t=this->m_siBestSchedule[i].actualStart;
		   int minute=t/60;
		   int second=t%60;

		   if(minute<10)
		      cout<<0;	   
		   cout<<minute<<":";

           if(second<10)
		      cout<<0;	 
		   cout<<second;

		   cout<<"  "<<this->m_siBestSchedule[i].index<<endl;
		  
	   }
	   cout<<endl;
   }
   else
   {
	   cout<<this->m_nRequestNum<<" requests have been successfully scheduled.\n";
	   cout.precision(3);
	   cout<<"The average waiting time is "<<double(this->m_giFcfs.totalWait)/this->m_nRequestNum
		   <<" minute(s).\n";
	   
	   for(int i=0;i<this->m_nRequestNum;i++)
	   {
		    int t=this->m_siFcfsSchedule[i].actualStart;
		   int minute=t/60;
		   int second=t%60;

		   if(minute<10)
		      cout<<0;	   
		   cout<<minute<<":";

           if(second<10)
		      cout<<0;	 
		   cout<<second;

		   cout<<"  "<<this->m_siFcfsSchedule[i].index<<endl;
		  
	   }
	   cout<<endl;
   }
  
}