（NOIP2016）交朋友

根据社会学研究表明，人们都喜欢找和自己身高相近的人做朋友。现在有n名身高两两不相间的同学依次走入教室，调查人员想预测每个人在走入教室的瞬间最想和已经进入教室的哪个人做朋友。当有两名同学和这名同学的身高差一样时，这名同学会更想和高的那个人做朋友。比如一名身高为1.80米的同学进入教室时，有一名身高为1.79米的同学和一名身高为1.81米的同学在教室里，那么这名身高为1.80米的同学会更想和身高为1.81米的同学做朋友。对于第一个走入教室的同学我们不作预测。

#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 ( ① ) {
            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];
        ② ;
    }
    for (i=n;i>=2;i--) {
        higher=shorter=infinity;
        if (previous[i]!=0)
            shorter=height[i]-height[previous[i]];
        if (next[i]!=0)
            ③ ;
        if ( ④ )
            answer[i]=previous[i];
        else
            answer[i]=next[i];
        next[previous[i]]=next[i];
        ⑤ ;
    }
    for (i=2;i<=n;i++)
        cout<<answer[i]<<" ";
    return 0;
}

①处应填（ ）。
{{ select(1) }}

• i<j
• i>j
• i<=j
• i>=j

②处应填（ ）。
{{ select(2) }}

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

③处应填（ ）。
{{ select(3) }}

• higher=height[next[i]]-height[i]
• higher=height[i]-height[previous[i]]
• higher=max(higher,height[next[i]]-height[i])
• higher=min(higher,height[next[i]]-height[i])

④处应填（ ）。
{{ select(4) }}

• shorter<=higher
• shorter<higher
• answer[i]>previous[i]
• answer[i]<previous[i]

⑤处应填（ ）。
{{ select(5) }}

• next[previous[i]]=next[i]
• previous[next[i]]=previous[i]
• previous[next[i]]=next[i]
• next[next[i]]=next[i]