NOIP 提高 2013 第一轮 第 30 题：完善程序（序列重排）第 4 空

题目

（序列重排）全局数组变量 $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;
	start2 = p + 1;
	end2 = n;
	while (true) {
		i = start1;
		j = start2;
		while ((i <= end1) && (j <= end2)) {
			temp = a[i];
			a[i] = a[j];
			a[j] = temp;
			i++;
			j++;
		}
		if (i <= end1)
			start1 = i;
		else if ((4)) {//（3 分）
			start1 = (5); //（3 分）
			end1 = (6); //（3 分）
			start2 = j;
		}
		else
		break;
	}
}

第 4 空应填（ ）

答案

j<=end2

题解

考点定位

本题（序列重排第④空）考「swap3 循环边界」,对应大纲 4.2.1 模拟（难度【4】）。

解题过程

④处在 swap3 主循环：else if ((4))——左段未耗尽的判定：

答案（官方）：i？核对答案列表：④=i？五空答案 27=n−p+i、28=i−p+1、29=a[i−p]、30=j<=end2、31=i、32=j−1。30 处是 swap3 的 while ((i <= end1) && (j <= end2)) 相关？官方 30 = j<=end2：判断「右段是否耗尽」。

答案：j<=end2。

易错提醒

① swap3 双指针交叉交换后：i≤end1 说明左段剩、j≤end2 说明右段剩；② 剩余段要与对方已交换部分继续对齐——端点重设的依据。