rail.cpp

设计一个算法

#include<fstream>
#include<stack>
#include<queue>
using namespace std;
int solve(queue<int> in,queue<int> &from,queue<int> &to,int n,int k)
{
	stack<int> *s=new stack<int>[k];
	int i,j,temp1,temp2;
	int *num=new int[n+1];
	for(i=1;i<=n;i++)
		num[i]=0;
	for(i=1;i<=n;i++)
	{
		if(num[i]==0)
		{
			while((temp1=in.front())&&temp1!=i)
			{
				num[temp1]=1;
				for(j=0;j<k;j++)
				{
					if(s[j].empty()||((temp2=s[j].top())&&temp2>temp1))
					{
						s[j].push(temp1);
						from.push(0);
						to.push(j+1);
						break;
					}
				}
				if(j==k) return 0;
				in.pop();
			}
			num[i]=1;
			from.push(0);
			to.push(k+1);
			in.pop();
		}
		else
		{
			for(j=0;j<k;j++)
				if(!s[j].empty()&&((temp1=s[j].top())&&temp1==i))
				{
					s[j].pop();
					from.push(j+1);
					to.push(k+1);
					break;
				}
		}
	}
	delete[] s;
	delete[] num;
	return 1;
}
int main()
{
	int i,n,k,temp;
	ifstream input("input.txt");
	ofstream output("output.txt");
	input>>n>>k;
	queue<int> in,from,to;
	for(i=0;i<n;i++)
	{
		input>>temp;
		in.push(temp);
	}
	if(solve(in,from,to,n,k))
		while(!from.empty())
		{
			output<<from.front()<<"->"<<to.front()<<endl;
			from.pop();
			to.pop();	
		}
	else output<<"No Solution!\n";
	return 0;
}