信息奥赛题解｜排列

---

🚀 题目浏览

【题目描述】

大家知道，给出正整数 $n$，则 $1$ 到 $n$ 这 $n$ 个数可以构成 $n!$ 种排列，把这些排列按照从小到大的顺序（字典顺序）列出，如 $n=3$ 时，列出 1 2 3，1 3 2，2 1 3，2 3 1，3 1 2，3 2 1 六个排列。

给出某个排列，求出这个排列的下 $k$ 个排列，如果遇到最后一个排列，则下 $1$ 排列为第 $1$个排列，即排列 1 2 3…n。

比如：$n = 3，k=2$ 给出排列 2 3 1，则它的下 $1$ 个排列为 3 1 2，下 $2$ 个排列为 3 2 1，因此答案为 3 2 1。

【输入】

第一行是一个正整数 $m$，表示测试数据的个数，下面是m组测试数据，每组测试数据第一行是 $2$ 个正整数 $n(1 \le n \lt 1024 ) $和 $k(1 \le k \le 64)$，第二行有 $n$ 个正整数，是 1，2 … n的一个排列。

【输出】

对于每组输入数据，输出一行，n个数，中间用空格隔开，表示输入排列的下k个排列。

【输入样例】

3
3 1
2 3 1
3 1
3 2 1
10 2	
1 2 3 4 5 6 7 8 9 10

【输出样例】

3 1 2
1 2 3
1 2 3 4 5 6 7 9 8 10

【题目来源】

https://vjudge.net/problem/POJ-1833

---

☘️ 题解分析

结合 STL 中的 next_permutation() 使用，效果巨佳。

PS：POJ 上不能使用万能头，想要使用 next_permutation()，需要添加 <algorithm> 头文件。

---

🧑🏻‍💻 C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;
const int N = 1100;
int n, a[N], T, k;

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    cin >> T;
    while (T--) {
        // 读入数据
        cin >> n >> k;
        for (int i = 1; i <= n; i++) cin >> a[i];

        // 利用next_permutation()函数，自动求下一个排列
        // next_permutation()会自动从最后一个排列回到第一个
        while (k--) next_permutation(a + 1, a + n + 1);

        // 输出结果
        for (int i = 1; i <= n; i++) cout << a[i] << " ";
        cout << endl;
    }

    return 0;
}