洛谷 P1088 火星人

这个题其实就是一个求全排列的问题，全排列的话在 algorithm 库里有一个非常好用的函数——next_permutation。

先介绍一下这个函数怎么用：

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 int a[3]={1,2,3};
 5 int main()
 6 {
 7     do
 8     {
 9         cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
10     }
11     while(next_permutation(a,a+3));
12     return 0;
13 }

运行结果：

这段代码就是求1,2,3全排列的，如果将while里的 next_permutation(a,a+3) 改为 next_permutation(a,a+2) ：

可以看出：改后，只是对数组的前两个数进行了排列，所以：next_permutation(a,a+n) 就是对 a 数组的前 n 个数进行排列，并且是按由小到大的顺序进行排列，同时也会更新数组。

这个题也就可以转化为求所给的 n 个数的后 m 个排列是什么。

代码：

 1 #include<iostream>
 2 #include<algorithm>// 函数必须的头文件
 3 using namespace std;
 4 int s[10010];
 5 int main()
 6 {
 7     int m,n;
 8     cin>>m>>n;
 9     for(int i=0;i<m;++i)
10     {
11         cin>>s[i];
12     }
13     for(int i=1;i<=n;++i)//进行 n 次排列
14     {
15         next_permutation(s,s+m);
16     }
17     for(int i=0;i<m;++i)
18     {
19         cout<<s[i]<<" ";
20     }
21     return 0;
22 }