railk-姜.cpp

设计一个算法

#include<iostream>
#include<fstream> 
template<class T>
class Stack
{
    private:
		int top;
		int MaxTop;
		T *stack;		
	public:
		Stack(int n=10);
		~Stack(){delete [] stack;}
		bool Empty() const {return top==-1;}
		bool Full() const {return top==MaxTop;}
		T Top() const;
		Stack<T>& Push(const T &x);
		Stack<T>& Pop(T &x);		   		
};
template<class T>
Stack<T>::Stack(int n)
{
	MaxTop=n-1;
	stack=new T[n];
	top=-1;	
}
template<class T>
T Stack<T>::Top() const
{
	return stack[top];
}
template<class T>
Stack<T>& Stack<T>::Push(const T &x)
{	
	stack[++top]=x;
	return *this;
}
template<class T>
Stack<T>& Stack<T>::Pop(T &x)
{	
	x=stack[top--];
	return *this;
}
using namespace std;
int main()
{
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    if(!fin.is_open()){
        fout<<"error"<<endl;
        exit(1);
    }
    int n;
    while(fin>>n){
        Stack<int> **table=new Stack<int>*[n];
		int i;
        for(i=0;i<n;i++)
            table[i]=0;
        table[0]=new Stack<int>(n);
        int temp;
        int *num=new int[n];
        for(i=0;i<n;i++)
            fin>>num[i];            
        for(i=n-1;i>=0;i--)
            table[0]->Push(num[i]);
        int now=1,count=0;
        while(now<n){
            bool find=false;
            for(int i=0;i<now;i++){
                if(!table[i])
                    break;
                if(table[i]->Empty())
                    continue;
                if(table[i]->Top()==now){
                    find=true;
                    now++;
                    table[i]->Pop(temp);
                    break;
                }
            }
            if(!find){
                table[0]->Pop(temp);
                for(int i=1;i<temp;i++){
                    if(!table[i]){
                        count++;
                        table[i]=new Stack<int>(n);
                        table[i]->Push(temp);
                        break;
                    }
                    else if(table[i]->Empty()){
                        table[i]->Push(temp);
                        break;
                    }
                    else if(temp<table[i]->Top()){
                        table[i]->Push(temp);
                        break;
                    }
                }
            }
        }
        fout<<count<<endl;
        delete []num;
        for(i=0;i<n;i++)
            delete table[i];
        delete []table;
    }            
    fin.close();
    fout.close();
    return 0;
}