railk.cpp

设计一个算法

#include <iostream>
#include <fstream.h>
#include <iomanip.h>
#include <exception>

template <class T> class Stack;

template<class T>
class Node{
	friend class Stack<T>;
	private:
		T data;
		Node<T> *next;
};

template<class T>
class Stack
{
	public:
		Stack(){top=0;}
		~Stack();
		bool Empty()const
		{return top==0;}
		bool Full()const;
		T Top()const;
		Stack<T>&Push(const T& x);
		Stack<T>&Pop(T& x);
	private:
		Node<T> *top;
};

template<class T>
Stack<T>::~Stack()
{
	Node<T> *next;
	while(top)
	{
		next=top->next;
		delete top;
		top=next;
	}
}
template<class T>
bool Stack<T>::Full ()const
{
	try{
		Node<T> *p=new Node<T>;
		delete p;
		return false;
	}
	catch(NoMem)
	{return true;}
}
template <class T>
T Stack<T>::Top()const
{
	if(Empty())
		exit(1);
	return top->data;
}
template<class T>
Stack<T>& Stack<T>::Push (const T& x)
{
	Node<T> *p=new Node<T>;
	p->data=x;
	p->next=top;
	top=p;
	return *this;
}
template<class T>
Stack<T> &Stack<T>::Pop(T& x)
{
	if(Empty())
		exit(1);
	x=top->data;
	Node<T> *p=top;
	top=top->next;
	delete p;
	return *this;
}



void Out(int& minH,int& minS,Stack<int> H[],int k,int n)
{
	int c;
	H[minS].Pop(c);
	minH=n+2;
	for(int i=1;i<=k;i++)
	{
		if(!H[i].Empty()&&(c=H[i].Top())<minH)
		{
			minH=c;
			minS=i;
		}
	}
}


bool Hold(int c,int& minH,int &minS,Stack<int> H[],int k,int n)
{
	int besttrack=0,besttop=n+1,x,i;
	for(i=1;i<=k;i++)
	{
		if(!H[i].Empty ())
		{
			x=H[i].Top();
			if(c<x && x<besttop)
			{
				besttop=x;
				besttrack=i;
			}
		}
		else
			if(!besttrack)
				besttrack=i;
	}
	if(!besttrack)
		return false;
	H[besttrack].Push(c);
	if(c<minH)
	{
		minH=c;minS=besttrack;
	}
	return true;
}
	

bool Railroad(int p[],int n,int k)
{
	Stack<int> *H;
	H=new Stack<int> [k+1];
	int nOut=1;
	int minH=n+1,minS,i;
	
	for(i=1;i<=n;i++)
	{
		if(p[i]==nOut)
		{
			nOut++;
		
		  while(minH==nOut)
		  {
			Out(minH,minS,H,k,n);
			nOut++;
		  }
		}
		else
		{
			if(!Hold(p[i],minH,minS,H,k,n))
				return false;
		}
	}
	return true;
}

void main()
{

    ifstream input("input.txt");
	ofstream output("output.txt");
	
     if(!input.is_open())
	 {
        output<<"input.txt is not exist"<<endl;
        exit(1);
    }
    int n,i,k;

    input>>n;
	if (n<1)
	{
		output<<"errer!"<<endl;
		exit(1);
	}

	int *p=new int[n];
	for(i=1;i<=n;i++)
	{
		input>>p[i];
	}
	

	for(k=0;k<=n;k++)
	{
		if(Railroad(p,n,k))
		{
			output<<k;
			break;
		}
	}
}