railkk.cpp

设计一个算法

#include<iostream>
#include<fstream>
class Select{
    public:        
        int data;
        int cap;
};
template<class T>
class Stack
{
    private:
		int top;
		int MaxTop;
		int leave;
		T *stack;
	public:
		Stack(int n=10);
		~Stack(){delete [] stack;}
		bool Empty() const {return top==-1;}
		bool Full() const {return top==MaxTop;}
		int cap()const{return leave;}
		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;	
	leave=n;
}
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;
	leave--;
	return *this;
}
template<class T>
Stack<T>& Stack<T>::Pop(T &x)
{	
	x=stack[top--];
	leave++;
	return *this;
}
void selsort(Select *num,int n)
{
    int i,j,k;
    Select t;
    for(i=0;i<n-1;i++){
        k=i;
        for(j=i+1;j<n;j++){
            if(num[j].cap>num[k].cap)
				k=j;
        }
        if(k!=i){
            t=num[i];num[i]=num[k];num[k]=t;
        }
    }
}                
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];        
        table[0]=new Stack<int>(n);
        int temp;
        int *num=new int[n];
		int i;
        for(i=0;i<n;i++)
            fin>>num[i];
        for(i=n-1;i>=0;i--)
            table[0]->Push(num[i]);
        for(i=1;i<=k;i++){
            fin>>temp;
            table[i]=new Stack<int>(temp);
        }
        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);
                int j=0;
                Select *sel=new Select[k];
                for(int i=1;i<=k;i++){
                    if(table[i]->Full() || temp>table[i]->Top())continue;
                    else{
                        sel[j].data=i;
                        sel[j++].cap=table[i]->cap();
                        find=true;
                    }
                }
                if(find){
                    selsort(sel,j);
                    int right=n-temp>j-1?j-1:n-temp;
                    table[sel[right].data]->Push(temp);
                    in_out[index][0]=0;
                    in_out[index++][1]=sel[right].data;
                }
                delete []sel;
            }
            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;
}