rail-姜.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,k;
    while(fin>>n>>k){
        Stack<int> **table=new Stack<int>*[k+1];
        int (*in_out)[2]=new int[n+n][2];
		int i;        
        for(i=0;i<=k;i++)
            table[i]=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,index=0;
        bool find;
        while(now<=n){
            find=false;
            for(int i=0;i<=k;i++){                
                if(table[i]->Empty())
                    continue;
                if(table[i]->Top()==now){
                    find=true;
                    now++;
                    table[i]->Pop(temp);
                    in_out[index][0]=i;
                    in_out[index++][1]=k+1;
                    break;
                }
            }
            if(!find){
                table[0]->Pop(temp);
                for(int i=1;i<=k;i++){
                    if(table[i]->Empty()){
                        table[i]->Push(temp);
                        in_out[index][0]=0;
                        in_out[index++][1]=i;
                        find=true;
                        break;
                    }
                    else if(temp<table[i]->Top()){
                        table[i]->Push(temp);
                        in_out[index][0]=0;
                        in_out[index++][1]=i;
                        find=true;
                        break;
                    }
                }
            }
            if(!find){
                fout<<"No Solution!"<<endl;
                break;
            }    
        }
        if(find){
            for(int i=0;i<index;i++)
                fout<<in_out[i][0]<<"->"<<in_out[i][1]<<endl;
        }           
        delete []num;
        for(i=0;i<=k;i++)
            delete table[i];
        delete []table;
        delete []in_out;        
    }            
    fin.close();
    fout.close();
    return 0;
}