排列按字典序对应整数，加 M 就是做 M 次 next_permutation：找枢轴、换最小可增大者、反转降序后缀，单步 O(N)，总复杂度 O(NM)。
OJ: roj
题目 ID: 3531
难度:普及
标签:模拟排列next_permutation
创建: 2026-10-02 05:39
更新: 2026-10-06 13:16
题目描述
思路
把排列看作康托展开的序号，加上
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 05:39
# update_at: 2026-10-02 05:39
import sys
def next_permutation(a: list[int]) -> None:
"""原地求字典序的下一个排列：把排列当作数，做一次 +1。
从右往左找第一个小于右邻的位置 i（其后缀是降序、已是后缀最大），
再从右往左找第一个大于 a[i] 的 j 交换，最后把降序后缀反转成升序最小。
"""
i = len(a) - 2
while i >= 0 and a[i] >= a[i + 1]:
i -= 1
if i < 0: # 已是全局最大排列；题面保证不会出现，兜底不动
return
j = len(a) - 1
while a[j] <= a[i]:
j -= 1
a[i], a[j] = a[j], a[i]
a[i + 1:] = a[:i:-1] # 交换后后缀仍降序，反转即得最小后缀
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
m = next(data) # 要加的小整数，相当于做 m 次"后继"
a = [next(data) for _ in range(n)]
for _ in range(m): # M ≤ 100，逐次 +1 总计 O(N·M)
next_permutation(a)
print(' '.join(map(str, a)))
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-06 13:11
* update_at: 2026-10-06 13:11
*/
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 10005;
int n, m;
int a[MAXN]; // 当前排列
// 原地求字典序下一个排列，O(n)
void next_permutation() {
int i = n - 2;
while (i >= 0 && a[i] >= a[i + 1]) i--; // 从右找第一个 a[i] < a[i+1]
if (i < 0) return; // 已是最大排列，题面保证不会出现
int j = n - 1;
while (a[j] <= a[i]) j--; // 从右找第一个大于 a[i] 的数
swap(a[i], a[j]); // 交换，让第 i 位增大得尽量少
// 反转降序后缀 a[i+1..n-1] 为升序最小
int l = i + 1, r = n - 1;
while (l < r) {
swap(a[l], a[r]);
l++;
r--;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < m; i++) next_permutation(); // 做 m 次后继
for (int i = 0; i < n; i++) {
if (i) cout << ' ';
cout << a[i];
}
cout << '\n';
return 0;
}