[NOIP 2004 普及组] 火星人

GitHub跳转原题关系图返回列表

手写原地 next permutation，连续执行 M 次，得到当前排列之后第 M 个字典序排列。

OJ: luogu

题目 ID: P1088

难度:普及-

标签:排列模拟python

日期: 2026-07-15 21:40

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

给定 1..N 的一个排列，以及一个很小的整数 M。要求输出这个排列在字典序中向后移动 M 次后的排列。

N 可以到 10000，不能生成所有排列。

思路

需要手写“下一个排列”。

从右往左看，找到第一个还能变大的位置 i，也就是：

text
a[i] < a[i + 1]

此时 i 右边的后缀是降序的。为了得到刚好大一点的排列：

  1. 在后缀中从右往左找第一个大于 a[i] 的数；
  2. 交换它和 a[i]；
  3. 把后缀反转成升序。

因为 M <= 100，执行 M 次 next_permutation 即可。

Python 知识

  • 列表可以原地交换：a[i], a[j] = a[j], a[i]。
  • 切片赋值 a[i + 1:] = reversed(a[i + 1:]) 可以把后缀反转后写回原列表。
  • print(*numbers) 用空格输出整个排列。

参考笔记：

  • /home/rainboy/mycode/hugo-blog/content/program_language/python/sorting_and_ordering.md
  • /home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md

代码

python
def next_permutation(a):
    n = len(a)
    i = n - 2
    while i >= 0 and a[i] > a[i + 1]:
        i -= 1

    j = n - 1
    while a[j] < a[i]:
        j -= 1

    a[i], a[j] = a[j], a[i]
    a[i + 1:] = reversed(a[i + 1:])


n = int(input())
m = int(input())
numbers = list(map(int, input().split()))

for _ in range(m):
    next_permutation(numbers)

print(*numbers)
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-07-27 00:00
 * update_at: 2026-07-27 00:00
 */
#include <bits/stdc++.h>
using namespace std;

int n, m;
int a[10005];

void next_perm() {
    int i = n - 2;
    while (i >= 0 && a[i] > a[i + 1]) i--;
    int j = n - 1;
    while (a[j] < a[i]) j--;
    swap(a[i], a[j]);
    reverse(a + i + 1, a + n);
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int t = 0; t < m; t++) next_perm();
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

复杂度

一次 next_permutation 是 O(N)O(N)，执行 M 次，总时间复杂度为 O(MN)O(MN)。空间复杂度为 O(N)O(N)。

总结

这题不能把所有排列列出来，而是要掌握字典序下“下一个排列”的局部修改规则。