NOIP 普及 2013 第一轮 第 27 题：将序列前后两段对调：第 1 空

题目

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

const int 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[①] = a[i];             //  （3分）
	for ( i = p + 1; i <= n; i++ )
		b[i - p] = ②;           //  （3分）
	for ( i = 1; i <= ③; i++ )  //  （2分）
		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 >= ④; j-- )    //  （ 3 分）
			a[j] = a[j - 1];
		⑤ = temp;                     // （ 3 分）
	}
}

①处应填（ ）

答案

n-p+i

题解

考点定位

本题（完善程序「序列重排」第①空）考「朴素重排的目标下标」,对应大纲 4.2.1 模拟（难度【3】）。

解题过程

swap2 的 O(n²) 做法：对 i=p+1..n，把 a[i] 前插到位置 j…；其中 b[(1)] 处（swap1 版本）存前段：b[n−p+i]=a[i]？官方①为 n-p+i：前段 a[1..p] 放入 b[n−p+1..n]（对调后前段变后段）。

答案：n−p+i。

易错提醒

① 对调后：原前段（p 个）放到尾部 ⇒ 目标下标从 n−p+1 开始；② b[n−p+i] 与 i 从 1 起对齐。