NOIP 提高 2016 第一轮 第 28 题：完善程序（交朋友）第 2 空

题目

（交朋友）根据社会学研究表明，人们都喜欢找和自己身高相近的人做朋友。现在有 $n$ 名身高两两不相同的同学依次走入教室，调查人员想预测每个人在 走入教室的瞬间最想和已经进入教室的哪个人做朋友。当有两名同学和这名 同学的身高差一样时，这名同学会更想和高的那个人做朋友。比如一名身高为 $1.80$ 米的同学进入教室时，有一名身高为 $1.79$ 米的同学和一名身高为 $1.81$ 米的同学在教室里，那么这名身高为 $1.80$ 米的同学会更想和身高为 $1.81$ 米的同学做朋友。对于第一个走入教室的同学我们不做预测。由于我们知道所有人的身高和走进教室的次序，所以我们可以采用离线的做法来解决这样的问题，我们用排序加链表的方式帮助每一个人找到在他之前进入教室的并且和他身高最相近的人。（第一空 $2$ 分，其余 $3$ 分）

#include <iostream>
using namespace std;
#define MAXN 200000
#define infinity 2147483647
int answer[MAXN], height[MAXN], previous[MAXN], next[MAXN];
int rank[MAXN];
int n;
void sort(int l, int r)
{
    int x = height[rank[(l + r) / 2]], i = l, j = r, temp;
    while (i <= j)
    {
        while (height[rank[i]] < x)
            i++;
        while (height[rank[j]] > x)
            j--;
        if ((1))
        {
            temp = rank[i];
            rank[i] = rank[j];
            rank[j] = temp;
            i++;
            j--;
        }
    }
    if (i < r)
        sort(i, r);
    if (l < j)
        sort(l, j);
}
int main()
{
    cin >> n;
    int i, higher, shorter;
    for (i = 1; i <= n; i++)
    {
        cin >> height[i];
        rank[i] = i;
	}
	sort(1, n);
	for (i = 1; i <= n; i++)
	{
		previous[rank[i]] = rank[i - 1];
		(2);
	}
	for (i = n; i >= 2; i--)
	{
		higher = shorter = infinity;
		if (previous[i] != 0)
			shorter = height[i] - height[previous[i]];
		if (next[i] != 0)
			(3);
		if ((4))
			answer[i] = previous[i];
		else
			answer[i] = next[i];
		next[previous[i]] = next[i];
		(5);
	}
	for (i = 2; i <= n; i++)
		cout << i << ":" << answer[i];
	return 0;
}

第 2 空应填（ ）

答案

next[rank[i]]=rank[i+1]

题解

考点定位

本题（交朋友第②空）考「链表初始化」,对应大纲 3.2.3 链表（难度【4】）。

解题过程

②处按排名串链：

``cpp next[rank[i]] = rank[i+1]; ``

（按身高序把相邻排名互连。）答案：next[rank[i]]=rank[i+1]。

易错提醒

① rank[i] 是身高第 i 矮的人；② 链表按身高升序串接后，倒序删除实现「找已入场者」。