NOIP 提高组初赛 · NOIP 2013 提高组初赛试题 第 27 题

（序列重排）全局数组变量 $a$ 定义如下：

#define SIZE 100 
int a[SIZE], n; 

它记录着一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$。 现在需要一个函数，以整数 $p(1 \leq p \leq n)$ 为参数，实现如下功能：将序列 $a$ 的前 $p$ 个数与后 $n - p$ 个数对调，且不改变这 $p$ 个数（或 $n - p$ 个数）之间的相对位置。例如， 长度为 $5$ 的序列 $1, 2, 3, 4, 5$，当 $p = 2$ 时重排结果为 $3, 4, 5, 1, 2$。

有一种朴素的算法可以实现这一需求，其时间复杂度为 $O(n)$、空间复杂度为 $O(n)$：

void swap1(int p) {
	int i, j, b[SIZE]; 
	for (i = 1; i <= p; i++)b[(1)] = a[i]; //（2 分） 
	for (i = p + 1; i <= n; i++)
		b[i - p] = a[i]; 
	for (i = 1; i <= n; i++)
		a[i] = b[i]; 
}

我们也可以用时间换空间，使用时间复杂度为 $O(n^2)$、空间复杂度为 $O(1)$的算法：

void swap2(int p) {
	int i, j, temp; 
	for (i = p + 1; i <= n; i++) {
		temp = a[i]; 
		for (j = i; j >= (2); j--)//（2 分） 
			a[j] = a[j - 1]; (3) = temp; //（2 分） 
	}
}

事实上，还有一种更好的算法，时间复杂度为 $O(n)$、空间复杂度为 $O(1)$：

void swap3(int p) {
	int start1, end1, start2, end2, i, j, temp; 
	start1 = 1; 
	end1 = p; 
	st

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

这题考数组原地重排，核心是swap3的区间调整逻辑，抓住前后段成对交换后剩余部分的边界更新，填对空就通了。

swap3里最容易错的是第4空和第5空：第4空漏写j<=end2，导致后面段还有数时程序直接break，前段剩下的数永远挪不动；第5空把start1写成j或end1+1，区间起点错位，整个平移就乱套。还有第6空把end1写成end2或start2，区间长度算错，越界或漏掉元素。

这道题考查数组操作中的原地重排，核心是swap3函数如何通过成对交换实现前p个与后n-p个的平移。命题人喜欢挖空在区间边界更新上，因为这是逻辑最抽象、最容易手滑的地方。拿到题先想：swap1用辅助数组，swap2用逐个插入（O(n²)），swap3是最优的O(n)O(1)，本质是前后两段不断成对交换，直到某一段空了，再把剩下的一段整体移到另一段末尾。具体怎么推？外层while(true)里，i和j分别指向前后段的当前元素，内层while成对交换a[i]和a[j]，i、j同步右移。当内层结束时，要么前后段都空了（i>end1且j>end2），要么只剩前段（i<=end1），要么只剩后段（j<=end2）。第4空就是判断后段是否还有剩余，填j<=end2；若为真，说明前段已空，后段剩下的要整体移到前段末尾，所以start1应填i（前段已处理完的下一个位置），end1填end1+1（前段长度加1），start2填j（后段剩余起点）。这样整个平移就完整了。逐空验证：第1空b[n-p+i]或b[i-p+n]都行，本质是把前p个存到后半段起始位置；第2空j的下限是i-p+1，因为要把a[i]往前挪到a[i-p]的位置；第3空a[i-p]=temp，把临时值放回目标位；第4空j<=end2，第5空i，第6空end1+1。考频上，一维数组是高频考点，2023年考了27题，2024年48题，2025年55题，2026年59题，逐年攀升，说明命题人越来越喜欢考数组操作的细节。未来可能继续考原地重排、区间移动这类需要细心边界处理的题目，尤其是GESP高级别和NOIP提高组初赛里这类题占比不小。总之，swap3的精髓就是抓住前后段剩余判断和区间更新，填对这几个空，这道题就稳了。