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

题目

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

第 2 空应填（ ）

答案

i-p+1

题解

考点定位

本题（序列重排第②空）考「swap2 插入边界」,对应大纲 4.2.1 模拟（难度【4】）。

解题过程

②处 swap2 的插入目标：把 a[i] 前插后它落在第 i−p+1 位：

答案（官方）：i−p+1（对应 for (j=i; j>=(2); j--) a[j]=a[j-1]; 的边界——右端收缩到 i−p+1）。

易错提醒

① 前插 1 位后 a[i] 的新位置是 i−p+1（向前挪 p 位）；② j 循环从 i 递减到 i−p+1，移 p 个元素。