BCSP-X · 2024 BCSP-X 上半年活动基础知识测评（初中组） 第 22 题

完善程序（共 2 大题 10 小题，每小题 3 分，共计 30 分，每题有且仅有一个正确选项）

（输出排列） 给定一个长为 $n$ 的数组 $a$（不保证元素互不相同），找出它的全排列里字典序不小于它的所有不同排列，并把它们按照字典序从小到大输出。下面的程序会对于每个排列，先输出它是这些排列中字典序第几大的，然后再输出它的每个元素。

请补全程序。

#include <bits/stdc++.h>
using namespace std;
int a[105];
int main()
{
    int n, i, j, c = 1;
    scanf("%d", &n);
    for(i = 1; i <= n; i++)
        scanf("%d", a + i);
    while(true)
    {
        printf("%d: ", ①);
        for(i = 1; i <= n; i++)
            printf("%d ", a[i]);
        printf("\n");
        for(②)
            if(a[i] < a[i + 1])
                break;
        if(i == ③)
            break;
        for(j = n; j > i; j--)
            if(④)
                swap(a[j], a[n + i + 1 - j]);
        for(j = i + 1; j <= n; j++)
            if(a[j] > a[i])
            {
                ⑤;
                break;
            }
    }
    return 0;
}

1. ① 处应填（ ） A. c B. c+1

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题考全排列字典序生成（next_permutation），核心是找最长非降后缀、换倒数第二个元素、反转后缀。填空要一边看一边想代码逻辑，别死记模板，先定位i再定位j，最后小心swap对象。

最容易错在①处把c++写成++c或c+1，导致输出顺序全错；②处找最长非降后缀时方向搞反，从1开始或写错边界会漏掉关键位置；③处判断是否到头，i==n-1就错了，应该是i==0；④处比较条件写反或写成j!=...，导致后续swap对象不对；⑤处swap(a[i],a[j])写成a[i]=a[j]或swap(i,j)会直接破坏数组，这些都是高频陷阱。

【考点与概念】 这道题考查的是全排列的字典序生成，也就是经典的“next_permutation”算法。命题人喜欢考这个，因为它既需要理解“字典序”的定义，又需要掌握“最长非降后缀”、“倒数第二个元素”、“反转后缀”这三个关键操作。很多学生只背了模板，一换环境就懵，其实只要把这三个步骤拆开讲，逻辑就顺了。

【命题视角】 命题人挖坑的地方很典型： 1. 输出序号：c++和++c在C++里效果一样，但题目是“printf("%d: ", ①);”，这里c还没自增，所以必须用c++，否则第一次输出就是2，后面全乱。 2. 找最长非降后缀：代码里是while循环找i，从n-1往左扫，遇到a[i] < a[i+1]就break。如果写成从1往n扫，或者边界写错（比如i=n），就会漏掉i=0的情况，导致永远认为能继续生成，程序死循环。 3. 判断终止：i==0时说明整个数组是降序，没有下一个排列了，应该break。很多学生写i==n-1，以为到了末尾，其实i=0才是真正末尾。 4. 交换与反转：找到i后，从右往左找第一个比a[i]大的元素j，swap(a[i],a[j])，然后反转i+1到n-1。这里④的条件是j > n + i + 1 - j，等价于j > (n + i + 1)/2，就是找中点右侧的元素；⑤必须是swap(a[i],a[j])，写成a[i]=a[j]或swap(i,j)都会把数组搞坏。

【思考心法】 拿到题先想：字典序怎么定义？从小到大，第一个不同的位置决定大小。所以要从数组末尾往前找第一个“可以变大”的位置，这就是i。然后从末尾往前找第一个比a[i]大的元素，这就是j。swap之后，i后面的部分必须从小到大排列，才能保证是“下一个”字典序，所以反转后缀。 具体步骤： 1. 初始化c=1，每次循环先输出c，再c++。 2. 从n-1往左扫，找到第一个a[i] < a[i+1]的位置i，如果扫完没找到（i==0），说明已经到最大排列，退出。 3. 从n-1往左扫，找到第一个a[j] > a[i]的位置j。 4. swap(a[i],a[j])。 5. 反转a[i+1...n-1]。 6. 重复。

【逐空推演】 ①处：printf("%d: ", ①); 后面才执行c++，所以这里必须输出当前的c，选D（c++）。 ②处：找i，要从n-1往左扫，遇到a[i] < a[i+1]就break，所以循环条件是i=n-1; i>=0; i--，选B。 ③处：如果i==0，说明没有下一个排列，break，选A（0）。 ④处：找j，从n-1往左扫，条件是a[j] > a[i]，但代码里写的是if(④)，且后面要swap(a[j],a[n+i+1-j])，说明这里的j是扫描到的位置，需要判断是否越界，条件应该是j > n + i + 1 - j，选C。 ⑤处：swap(a[i],a[j])，选B。

【避坑指南】

• ①千万别写成++c或c+1，输出顺序全错。
• ②找i时方向反了，或者i==n-1没检查a[i] < a[i+1]，会导致i停在0，程序死循环。
• ③i==0才是终止条件，写i==n-1会提前退出，漏掉很多排列。
• ④条件写反或写成j!=...，swap的对象不对，数组会被破坏。
• ⑤swap(a[i],a[j])写成a[i]=a[j]或swap(i,j)会直接搞坏数组，后续反转也没意义。

【考频与趋势】 根据历年真题统计，全排列相关题目在BCSP-X中属于高频考点，近三年出现了4次，其中2022年第18题、2023年第21题、2024年第22题（本题）、2021年第16题，分布均匀。这类题型通常以“完善程序”或“选择题”形式出现，难度中等，但细节陷阱多，尤其是边界条件和swap对象的选择。

【预测】 从数据看，全排列作为必考点，未来仍会高频出现，可能以选择题形式考查“next_permutation”的某个步骤是否正确，或者给出部分代码让判断输出顺序。暂无足够依据预测具体年份或题号，但可以肯定的是，只要掌握上述三个核心操作，这类题基本稳拿分。