华为OJ火车进站

妖狐艹你老母 2022-06-17 10:56 153阅读 0赞

<table style="border-spacing:0px; border-collapse:collapse; width:960px; margin-bottom:35px; table-layout:fixed; color:rgb(92,92,92); font-family:glober,'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); background-color:rgb(226,243,253); width:872px"> <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); background-color:rgb(226,243,253); width:872px"> 栈</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); background-color:rgb(226,243,253); width:872px"> 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); background-color:rgb(226,243,253); width:872px"> 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); background-color:rgb(226,243,253); width:872px"> <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); background-color:rgb(226,243,253); width:872px"> <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); background-color:rgb(226,243,253); width:872px"> 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); background-color:rgb(226,243,253); width:872px"> 1 2 3 1 3 2 2 1 3 2 3 1 3 2 1</td> 
  </tr> 
 </tbody> 
</table>

#include <iostream>    
    #include <vector>
    #include <string>
    #include <deque>
    #include <stack>
    #include <map>
    #include <algorithm>
    
    using namespace std;
    
    //算法步骤：
    //（1）输入数组进行字典排序；
    //（2）判断字典排序数组是否符合进出栈要求。
    
    //函数名：isLexicographicalOrder
    //输入：原始输入数组origin，字典排序数组vec
    //输出：满足进出栈要求，返回true，否则，返回false
    bool isLexicographicalOrder(vector<int> &origin,vector<int> vec)
    {
    	stack<int> sta;
    	deque<int> deq;//双端队列deq存储字典排序数组
    	for (int i = 0; i < vec.size(); i++)
    		deq.push_back(vec[i]);
    
    	int index = 0;
    	while (!deq.empty())
    	{
    		if (index == origin.size())//如果条件满足，说明所有origin数组中的所有数据都已入栈，跳出
    			break;
    
    		while ((index < origin.size()) &&(sta.empty() || sta.top() != deq.front()))//模拟数据入栈
    		{
    			sta.push(origin[index]);
    			index++;
    		}
    
    		while (!sta.empty() && sta.top() == deq.front())//模拟数据出栈
    		{
    			sta.pop();
    			deq.pop_front();
    		}
    	}
    
    	if (deq.empty())
    		return true;
    	else
    		return false;
    }
    void main()
    {
    	int N;
    	vector<int> vec;
    	vector<int> origin;
    	cin >> N;
    	for (int i = 0; i < N; i++)
    	{
    		int tmp;
    		cin >> tmp;
    		vec.push_back(tmp);
    		origin.push_back(tmp);
    	}
    
    	sort(vec.begin(), vec.end());
    
    	do
    	{
    		if (isLexicographicalOrder(origin, vec))
    		{
    			for (int i = 0; i < vec.size()-1; i++)
    				cout << vec[i] << " ";
    			cout << vec[vec.size()-1] << endl;
    		}	
    	} while (next_permutation(vec.begin(), vec.end()));
    }