NOIP 普及组初赛 · NOIP 2009 普及组初赛试题 第 26 题

阅读程序写结果：

#include <iostream>
using namespace std;

const int maxn=50;
void getnext(char str[])
{
	int l=strlen(str),i,j,k,temp;
	k=l-2;
	while(k>=0&&str[k]>str[k+1]) k--;
	i=k+1;
	while(i<l&&str[i]>str[k]) i++;
	temp=str[k];
	str[k]=str[i-1];
	str[i-1]=temp;
	for(i=l-1;i>k;i--)
		for(j=k+1;j<i;j++)
			if(str[j]>str[j+1])
			{
				temp=str[j];
				str[j]=str[j+1];
				str[j+1]=temp;
			}
	return ;
}

int main()
{
	char a[maxn];
	int n;
	cin >> a >> n;
	while(n>0)
	{
		getnext(a);
		n--;
	}
	cout << a << endl;
	return 0;
}

输入：NOIP 3

这题考的是字典序下一个排列（next_permutation）。拿到程序先别急着看细节，直接模拟：把当前字符串当成一个数字，每次调用 getnext 就是把它变成下一个更大的数，循环 3 次后输出结果。

很多同学一看到代码里那个 while(k>=0&&str[k]>str[k+1]) 就慌了，以为是要找逆序对或者冒泡排序，其实这是在找‘第一个升序对’——从右往左扫，只要相邻两个字符是左小右大就停手。找到这个位置 k 后，代码接着从右边再扫一遍，找第一个比 str[k] 大的字符 str[i]，然后交换，最后把后缀反转。整个过程就是标准的‘下一个排列’三步走：找升序对→交换→反转后缀。如果只做到交换就以为结束了，或者把后缀当成升序直接输出，那就错了。

考点与命题视角

这题考查的是字典序下一个排列（C++ 标准库里的 next_permutation 功能）。命题人为什么选这个？因为它是信息学竞赛里非常经典的一个算法，代码量少但逻辑严密，特别适合考阅读程序写结果。它常出现在初赛填空题，也偶尔出现在提高组。命题人喜欢在细节上挖坑：比如找升序对的边界条件（str[k] > str[k+1]）、交换后后缀的排序（必须反转）、以及字符串长度和索引的越界问题。

算法原理解释（人话版）

想象一下，你手里有一组数字（或字母），比如 1234，你想把它变成下一个更大的数，但又不想跳太大。怎么做？

1. 从右往左找第一个“升序对”：就是找到两个相邻的数字，左边比右边小。比如 1234 里，3 和 4 就是一对。这个位置记作 k。 2. 在 k 右边找第一个比 str[k] 大的数字：比如 3 的右边只有 4，那就选 4。记作 i。 3. 交换这两个数字：把 3 和 4 换一下，得到 1243。 4. 把交换后的后缀反转：后缀原来是 43，反转后变成 34，最终得到 1234 → 1243 → 1234（这里只是演示，实际例子会不同）。

对于字母也一样，只是按字母表顺序比较。这个算法的核心就是：找升序对 → 交换 → 反转后缀。三步缺一不可。