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