题目描述
这里有 n列火车将要进站再出站,但是,每列火车只有 1 节,那就是车头。这 n 列火车按 1 到 n 的顺序从东方左转进站,这个车站是南北方向的,它虽然无限长,只可是一个死胡同,而且站台只有一条股道,火车只能倒着从西方出去,而且列火车必须进站,先进后出。
也就是说这个火车站其实就相当于一个栈,每次可以让右侧头火车进栈,或者让栈顶火车出站。
车站示意如图:
出站<—— <——进站
|车|
|站|
|__|
现在请你按《字典序》输出前 20 种可能的出栈方案。
输入格式
输入一个整数 n
,代表火车数量。
输出格式
按照《字典序》输出前 20
种答案,每行一种,不要空格。
数据范围
1≤n≤20
样例
输入样例:
3
输出样例:
123
132
213
231
321
题解:
由样例可知:输出是全排列的一部分。
123
132
213
231
321
(312)
而根据栈的性质可知若A在B后面出栈且A小于B,则一定是这样
|B|
|A|
|_|
而A后面若有n个比他小的数a1~an是这样的
|A |
|a1|
|a2|
|a3|
|. |
|. |
|. |
|an|
|__|
又因为先进栈的比后进栈的小,所以a1>a2>a3>…>an
而出栈后一定是 a1,a2,a3,…,an
所以可以得到一个性质:…A…a1…a2…a3......an(A最大)
a1~an一定是从小到大的
c++代码
#include<bits/stdc++.h>
using namespace std;
int n,t=0;
int a[25];
bool pd(){
for(int i=1;i<=n;i++){
int t=a[i];
for(int j=i+1;j<=n;j++){
if(a[j]<a[i]){
if(a[j]>t) return 0;
t=a[j];
}
}
}
return 1;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
a[i]=i;
}
do{
if(pd()){
for(int i=1;i<=n;i++){
cout<<a[i];
}
cout<<'\n';
t++;
if(t==20) return 0;
}
}while(next_permutation(a+1,a+n+1));
return 0;
}