railqkk.cpp

本程序是关于火车车皮调度问题

#include<iostream.h>
#include<fstream.h>
#define M 50
template<class T>
class queue{
	public:
		queue(const int& max1=10)
		{
  	      maxsize=max1+1;
	      queue1=new T[max1+1];
	      front=rear=0;
		}
	void cp(int max)
		{
			maxsize=max+1;
			queue1=new T[max+1];
		
		}
		bool empty()const{return front==rear;}
		bool full(){return(((rear+1)%maxsize==front)?1:0);}
		T first()const;
		T last()const;
		queue<T>&enqueue( const T& x);
		queue<T>&dequeue();
	private:
		int front;
		int rear;
		int maxsize;
		T* queue1;
};



template<class T>
T queue<T>::first()const
{
	if(empty())return 0;
	return queue1[(front+1)%maxsize];
}
template<class T>
T queue<T>::last()const
{
	if(empty())return 0;
	return queue1[rear];
}
template<class T>
queue<T>&queue<T>::enqueue( const T&x)
{
	rear=(rear+1)%maxsize;
	queue1[rear]=x;
	return *this;
}
template< class T>
queue<T>&queue<T>::dequeue()
{ 
	T x;
	front=(front+1)%maxsize;
	x=queue1[front];
	return *this;
}
int main()
{
	int n,k,x,nowout=1,w=1,j,i=0,entrance[M],out1[M],s=0,p,t;
	queue<int>queue2[M];
	ifstream in("input.txt");
	in>>n>>k;
	
	int *H=new int[n];
	for(j=0;j<n;j++)
	{
		in>>x;
		H[j]=x;
	}
	for(j=0;j<k-1;j++)
	{
		in>>p;
		
		queue2[j].cp(p);
	}
	j=0;
	while(s++<n)
	{
		if(nowout==H[j])
		{
			entrance[i]=0;
			out1[i++]=k;
			nowout++;
			for(t=1;t<w&&nowout<=n;t++)
			{
				if(nowout==queue2[t-1].first())
				{
					entrance[i]=t;
					out1[i++]=k;
					queue2[t-1].dequeue();
					nowout++;
					t=0;
				}
			}
		}
		else
		{
			for(t=1;t<w;t++)
			{
				if(queue2[t-1].last()<H[j]&&!(queue2[t-1].full()))
				{
					queue2[t-1].enqueue(H[j]);
					entrance[i]=0;
					out1[i++]=t;
					if(w==1)w++;
					break;
					
				}
			}
			if(t==w)
			{
				
				queue2[t-1].enqueue(H[j]);
				entrance[i]=0;
				out1[i++]=t;
				w++;
			}
			
		}
		j++;
	}
	ofstream out("output.txt");
	if(w>k)
	{
		out<<"No Solution!"<<endl;
		return 0;
	}

	if(nowout<=n)
	{
		for(t=1;t<=w&&nowout<=n;t++)
		{
			if(nowout==queue2[t-1].first())
			{
				entrance[i]=t;
				out1[i++]=k;
				queue2[t-1].dequeue();
			    nowout++;
				t=0;
			}
		}
	}
	for(t=0;t<i;t++)
		out<<entrance[t]<<"->"<<out1[t]<<endl;
	
	delete[]H;
	return 0;
}