railkk.cpp

本程序用于实系数一元项式问题

#include<fstream>
#include<iostream>
#define M 10000
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt"); 
class Node 
{
	friend class stack;
private:
	int data;
	Node *next;
};
class stack
{
public:  
	stack(){top=0;}
	~stack();
	bool Empty()const{return top==0;}
	int Top()const;
	stack &push(int x);
	stack &pop();
private:
	Node *top;	
};
stack::~stack()
{
	Node * next;
	while(top)
	{
		next=top-> next;
		delete top;
		top=next;
	}
}
int stack::Top()const
{
	if(Empty())
		return 0;
	return top->data;
}
stack&stack::push(int x)
{
	Node *p=new Node;
	p->data=x;
	p->next=top;
	top=p;
	return *this;
}
stack&stack::pop()
{
	int x;
	x=top->data;
	Node *p=top;
	top=top->next;
	delete p;
	return *this;
}
int main()
{
	stack track[M];
	int entrance[M],exit[M],shuchu=1,i=0,j,n,s=0,k,x,w=1;   //一开始让输出为1,表明因为输出一开始一定是从1开始的.并且用两个数字
	in>>n>>k;                                                                                     来存放每一步中车皮的起始栈和到达的栈
	while(s++<n)
	{
		in>>x;
		if(x==shuchu)       //如果第2行中,现在输出的数就是输出那边的数
		{
			entrance[i]=0;      //让起始数组开始为0
			exit[i++]=k+1;       //到达的栈为输出栈
			shuchu++;
			for(j=1;j<w&&shuchu<=n;j++)
			{
				if(track[j].Top()==shuchu)
				{
					entrance[i]=j;
					exit[i++]=k+1;
					track[j].pop();
					if(!track[j].Top ())
						track[j].push(n+1);
					shuchu++;					 
					j=0;
				}
			}
		}
		else              //数进来的数不是输出当中的数.
		{			
			for(j=1;j<w;j++)
			{					 
				if(x<track[j].Top ())       //尽量让数字望前面的栈进去
				{
					track[j].push(x);                   
					entrance[i]=0;
					exit[i++]=j; 
					break;
				}
			}
			if(j==w)
			{
				track[w++].push(x);
                entrance[i]=0;
			    exit[i++]=j;			 
			}			
		}		 
	}
	while(shuchu<=n)
	{
		for(j=1;j<w;j++)
			{			 
				if(track[j].Top()==shuchu)
				{
					entrance[i]=j;
					exit[i++]=k+1;
					track[j].pop();
					shuchu++;
					j=1;					
				} 
			}
	}
     if(w>k+1)
      	out<<"No solution!"<<endl;
     else
      	for(int s=0;s<i;s++)
       	   	out<<entrance[s]<<"->"<<exit[s]<<endl;
  	return 0;
}