NOIP 提高 2018 第一轮 第 24 题：枚举全排列求下一个排列

题目

阅读程序写结果：

#include <iostream>
using namespace std;
const int N = 110;
bool isUse[N];
int n, t;
int a[N], b[N];
bool isSmall() {
    for (int i = 1; i <= n; ++i)
        if (a[i] != b[i]) return a[i] < b[i];
    return false;
}
bool getPermutation(int pos) {
    if (pos > n) {
        return isSmall();
    }
    for (int i = 1; i <= n; ++i) {
        if (!isUse[i]) {
            b[pos] = i; isUse[i] = true;
            if (getPermutation(pos + 1)) {
                return true;
            }
            isUse[i] = false;
        }
    }
    return false;
}
void getNext() {
    for (int i = 1; i <= n; ++i) {
        isUse[i] = false;
    }
    getPermutation(1);
    for (int i = 1; i <= n; ++i) {
        a[i] = b[i];
    }

}
int main() {
    scanf("%d%d", &n, &t);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= t; ++i) {
        getNext();
    }
    for (int i = 1; i <= n; ++i) {
        printf("%d", a[i]);
        if (i == n) putchar(’\n’); else putchar(’ ');
    }
    return 0;
}

输入 1：6 10 1 6 4 5 3 2
请写出输出结果。

输入 2：6 200 1 5 3 4 2 6
请写出输出结果。

答案

213564; 325614

题解

考点定位

本题考「全排列搜索模拟」,对应大纲 4.3.3 搜索（难度【5】）。

解题过程

程序枚举全排列找「比输入排列大的下一个排列」的暴力版。输入 6 10 1 6 4 5 3 2 与 6 200 1 5 3 4 2 6：

输出 213564; 325614（两组输入各一，连写分号）。

易错提醒

① getNext 暴力枚举字典序下一个排列（isSmall 判定）；② t 次getNext = 连续应用 t 次后到达的排列；③ 与 std::next_permutation 结果对照验证。