华为OJ平台题目：火车进站

阳光穿透心脏的1/2处 2022-08-05 10:30 173阅读 0赞

<table style="border-spacing:0px; border-collapse:collapse; width:960px; margin-bottom:35px; table-layout:fixed; color:rgb(92,92,92); font-family:'Helvetica Neue',Helvetica,Arial,'Lantinghei SC','Hiragino Sans GB','Microsoft YaHei','Wenquanyi Micro Hei',sans-serif; font-size:14px; line-height:20px"> 
 <tbody style=""> 
  <tr style=""> 
   <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 描述</th> 
   <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); width:872px; background-color:rgb(226,243,253)"> <pre style="overflow:hidden; font-family:monospace,monospace; font-size:1em; white-space:pre-wrap; word-wrap:break-word; line-height:24px"><p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"><span style="white-space:normal">给定一个正整数N代表火车数量，0&lt;N&lt;10，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号。要求以字典序排序输出火车出站的序列号。</span><br style=""></p></pre> </td> 
  </tr> 
  <tr style=""> 
   <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 知识点</th> 
   <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); width:872px; background-color:rgb(226,243,253)"> 栈</td> 
  </tr> 
  <tr style=""> 
   <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 运行时间限制</th> 
   <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); width:872px; background-color:rgb(226,243,253)"> 0M</td> 
  </tr> 
  <tr style=""> 
   <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 内存限制</th> 
   <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); width:872px; background-color:rgb(226,243,253)"> 0</td> 
  </tr> 
  <tr style=""> 
   <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 输入</th> 
   <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); width:872px; background-color:rgb(226,243,253)"> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> <span style="">有多组测试用例，每一组第一行输入一个正整数N（0&lt;N&lt;10），第二行包括N个正整数，范围为1到9。</span><br style=""> </p> </td> 
  </tr> 
  <tr style=""> 
   <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 输出</th> 
   <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); width:872px; background-color:rgb(226,243,253)"> <p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px"> <span style="">输出以字典序排序的火车出站序列号，每个编号以空格隔开，每个输出序列换行，具体见sample。</span><br style=""> </p> </td> 
  </tr> 
  <tr style=""> 
   <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 样例输入</th> 
   <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); width:872px; background-color:rgb(226,243,253)"> 3 1 2 3</td> 
  </tr> 
  <tr style=""> 
   <th style="padding:8px 0px; font-weight:normal; width:86px; margin:1px; border:2px solid rgb(255,255,255); background-color:rgb(207,235,252)"> 样例输出</th> 
   <td style="padding:8px 20px; word-break:break-all; word-wrap:break-word; border:2px solid rgb(255,255,255); width:872px; background-color:rgb(226,243,253)"> 1 2 3 1 3 2 2 1 3 2 3 1 3 2 1</td> 
  </tr> 
 </tbody> 
</table>

**解题思路：先根据火车编号进行全排列，再判断该全排列是否符合要求，也就还是判断出栈的顺序是否符合要求**。

#include <iostream>
    #include <vector>
    #include <stack>
    
    using namespace std;
    
    
    /* 判断该出栈序列，是否符合要求 */
    bool isRight(int in[], int out[], int n)
    {
    	bool ret = true;
    	stack<int> sta;
    	int index_out = 0, index_in = 0;
    
    	while(index_out < n)
    	{		
    		while(index_in < n)
    		{
    			if(sta.empty())
    			{
    				sta.push(in[index_in]);
    				index_in++;
    			}
    			else if(sta.top() != out[index_out])
    			{
    				sta.push(in[index_in]);
    				index_in++;
    			}
    			else 
    			{
    				break;
    			}
    		}
    
    		if(sta.top() == out[index_out])
    		{
    			sta.pop();
    			index_out++;
    		}
    		else
    		{
    			break;
    		}
    
    	}
    	if(sta.empty())
    	{
    		ret = true;
    	}
    	else
    	{
    		ret = false;
    	}
    	
    	return ret;
    }
    
    /* 全排列 */
    void perm(int in_train[],int a[], int k, int n)
    {
    	int i = 0;
    	if(k == n)
    	{
    		/* 判断该序列是否符合要求 */
    		if(isRight(in_train,a,n) == true)
    		{
    			for(i = 0; i < n; i++)
    			{
    				
    				if(i == 0)
    				{
    					cout << a[i];
    				}
    				else
    				{
    					cout << " " << a[i] ;
    				}		
    			}
    			cout << endl;
    		}	
    	}
    	else
    	{
    		for(i = k; i < n; i++)
    		{
    			swap(a[i],a[k]);
    			perm(in_train,a,k+1,n);
    			swap(a[i],a[k]);
    		}
    	}
    }
    
    int main()
    {
    	int N = 0,i = 0;
    	/* 存放火车的编号 */
    	int data[10] = {0};
    	int data_bk[10] = {0};
    
    	cin >> N;
    	for(i = 0; i < N; i++)
    	{
    		cin >> data[i];
    		data_bk[i] = data[i];
    	}
    	perm(data_bk,data,0,N);
    
    
    	return 0;
    }