NOIP 提高组初赛 · NOIP 2014 提高组初赛试题 第 25 题

#include <stdio.h>
#include <string.h>
const int	SIZE	= 100;
const int	LENGTH	= 25;
/*
 * strcmp(a,b) <0:a的字典序小于b
 * strcmp(a,b) =0:a和b一样
 * strcmp(a,b) >0:a的字典序大于b
 */
int main()
{
	char	dict[SIZE][LENGTH + 1];
	int	rank[SIZE];
	int	ind[SIZE];
	int	i, j, n, tmp;
	scanf( "%d", &n );
	for ( i = 1; i <= n; i++ )
	{
		rank [i]	= i;
		ind[i]		= i;
		scanf( "%s", dict[i] );
	}
	for ( i = 1; i < n; i++ )
		for ( j = 1; j <= n - i; j++ )
			if ( strcmp( dict[ind[j]], dict[ind[j + 1]] ) > 0 )
			{
				tmp		= ind[j];
				ind[j]		= ind[j + 1];
				ind[j + 1]	= tmp;
			}
	for ( i = 1; i <= n; i++ )
		rank[ind[i]] = i;
	for ( i = 1; i <= n; i++ )
		printf( "%d ", rank[i] );
	printf( "\n" );
	return(0);
}

输入： 7 aaa aba bbb aaa aaa ccc aa 输出：______

别急着背冒泡排序的模板，这题考的是冒泡排序的'原地交换'怎么影响'原始位置'。核心思路是：先跑一遍排序把字符串排好序，但千万别直接输出排好序后的内容；要记录每个字符串在排序前是第几个输入的，排序结束后，按排好序的顺序把'原始序号'打印出来，这才是题目要的排名。

最容易栽跟头的地方是分不清'排序后的内容'和'原始输入顺序'。很多学生看到冒泡排完序是aaa,aaa,aaa,aba,bbb,ccc,aa，就以为答案就是这个顺序或者对应的字典序大小，完全忽略了题目问的是'原顺序的排名'。其次，冒泡排序里那个tmp交换的是下标ind[j]和ind[j+1]，而不是直接交换字符串，如果代码里写成了swap(dict[j], dict[j+1])，虽然排序结果一样，但后面用ind数组去查原始位置就全乱了。还有，最后输出循环里是rank[ind[i]] = i，这里rank数组的下标是排序后的位置，值才是原始序号，千万别把rank和ind搞反了，或者输出成rank[i]（那是排序后的字典序排名，不是题目要的）。

考点拆解与命题意图

这道题属于典型的'程序阅读+逻辑推理'类填空题。它表面上考的是冒泡排序，但命题人的心思其实不在排序算法本身，而在于考察考生对'排序稳定性'与'原始位置映射'的理解。

在NOIP/CSP这类信息学竞赛的初赛阶段，排序是高频考点（根据题库数据，2008-2026年间共考了249题，覆盖从入门到提高的各个级别，特别是2024、2025、2026年考频陡增，说明这类题目越来越受青睐）。命题人喜欢挖的坑通常有两个方向：一是算法细节（比如冒泡的循环边界、交换对象），二是数据流向（比如排序后如何还原原始信息）。这题就精准地踩中了第二个坑——它要求你输出的不是排好序的字符串，而是'每个字符串在原输入中的位置'。

代码逐行推演

我们先快速过一遍代码逻辑，看看它在做什么。

1. 定义与输入 - dict[SIZE][LENGTH + 1] 用于存储字符串，rank 和 ind 数组初始化为 1..n。这里 ind[i] = i 是个关键：它记录了第 i 个输入的字符串的原始位置。 - 读入 n 和 n 个字符串。注意，代码里 rank[i] = i 其实有点多余，因为后面根本没用到 rank 数组来存原始位置，它只用来最后赋值排名。真正的'原始位置记录器'是 ind。

2. 冒泡排序核心 ``c for ( i = 1; i < n; i++ ) for ( j = 1; j <= n - i; j++ ) if ( strcmp( dict[ind[j]], dict[ind[j + 1]] ) > 0 ) { tmp = ind[j]; ind[j] = ind[j + 1]; ind[j + 1] = tmp; } ` 这里有两个细节必须盯紧： - 交换的不是 dict[j] 和 dict[j+1]，而是 ind[j] 和 ind[j+1]。这意味着字符串数组 dict 里的内容其实从来没动过，动的只是 ind 数组里的下标。 - strcmp 比较的是 dict[ind[j]] 和 dict[ind[j+1]]`。也就是说，排序的依据是字符串的字典序，但交换的对象是'指向字符串的索引'。

这种写法的好处是：排序完成后，ind 数组里的顺序就是字符串排好序后的索引序列。比如排完序后 ind 可能是 [7, 1, 2, 3, 4, 6, 5]，这表示排好序后的第1个字符串是原输入的7号，第2个是1号，以此类推。

3. 计算排名 ``c for ( i = 1; i <= n; i++ ) rank[ind[i]] = i; ` 这一步是解题的关键。循环变量 i 代表'排序后的位置'，ind[i] 代表'这个位置对应的原始序号'。把 i 赋给 rank[ind[i]]，意思是：'原序号为 ind[i] 的那个字符串，它的排名是 i'。 举个例子，如果 ind[1] = 7，那么 rank[7] = 1`，说明原第7个输入的字符串排到了第1名。

4. 输出结果 ``c for ( i = 1; i <= n; i++ ) printf( "%d ", rank[i] ); ` 注意这里输出的是 rank[i]，而不是 ind[i]。rank[i] 的含义是'原序号为 i` 的那个字符串的排名'。题目问的正是这个：'第1个输入的字符串排第几？第2个输入的排第几？...'。所以最终输出的序列，就是按原输入顺序排列的'排名表'。