railk_优化.cpp

设计一个算法

#include<iostream>
#include<fstream> 
template<class T>
class Stack  
{
public:
    Stack(){Head = NULL;}
    ~Stack();
    void Push(T data);    
    bool Pop(T& data);
    T Top(){return Head->Data;}
    bool Empty(){return Head==NULL;}
protected:
    struct Node
    {
        T Data;
        Node* Next;
    };   
    Node* Head;
};
template<class T>
Stack<T>::~Stack()
{
    Node* pNode = Head;
    Node* temp;
    while(pNode){
        temp = pNode->Next;
        delete pNode;
        pNode = temp;
    }
}
template<class T>
void Stack<T>::Push(T data)
{
    Node* temp;
    temp = Head;
    Head = new Node;
    Head->Next = temp;
    Head->Data = data;
}
template<class T>
bool Stack<T>::Pop(T& data)
{
    if(Head){
        data = Head->Data;
        Node* temp = Head->Next;
        delete Head;
        Head = temp;
        return true;
    }
    else
        return false;
}
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>;
        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>;
                        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<=count;i++)
            table[i]->~Stack();
        delete []table;
    }            
    fin.close();
    fout.close();
    return 0;
}