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

题目

（序列重排）全局数组变量 $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;
	}
}

第 5 空应填（ ）

答案

i

题解

考点定位

本题（序列重排第⑤空）考「剩余段起点」,对应大纲 4.2.1 模拟（难度【4】）。

解题过程

⑤处 start1 重置（右段先耗尽时左段剩余继续）：

答案：i（当前 i 即左段剩余的起点）。

易错提醒

① 交叉交换一轮后：i 停在左段未处理处，且左段「多出」j−start2 个已就位元素 ⇒ start1 前移；② 官方答案 i 与 start1=(5) 的填空对应「start1 = i」语义。