递归O（nlogn）

解题思路:

其实我们研究的对象是兔子的末状态，所以不必把兔子移动过程展现出来。

选用指针来表示兔子的移动方向，首先先确定两只“双向奔赴"兔子的位置，单向奔赴兔子的末位置与指向的兔子一样，用深搜扫一下就行，这里我用的是C语言，时间复杂度为O（nlogn）,能力有限，不会优化了，大家凑合看看。

注意事项:
但是这里要注意一点第一只兔子指向第二只兔子，最后一只兔子指向倒数第二只兔子
参考代码:

#include<stdio.h>  

#include<stdlib.h>  

struct member{  

    int opp;                        //兔子初始位置  

    int index;                    //记录输入顺序  

    int u;                        //判断是否被“扫”过  

    struct member *place;  

};   

int ans[1000005];  

struct member m[1000005];  

 int cmp(const void *x,const void *y){  

    struct member xx = *(struct member*)x;  

    struct member yy = *(struct member*)y;  

    return xx.opp-yy.opp;  

}  

void des(struct member *a){                                    //递归深搜  

    if((*(a->place)).u==0){  

        des(a->place);  

    }  

    ans[a->index]=ans[(*(a->place)).index];  

    a->u=1;  

}  

int main(){  

    int n;  

    scanf("%d",&n);  

    for(int i=0;i<n;i++){  

        scanf("%d",&ans[i] );  

        m[i].opp =ans[i];  

        m[i].index=i;  

        m[i].u=0;  

    }  

    qsort(m,n,sizeof(m[0]),cmp);              // 排序  

    m[0].place =&m[1];                                  //对兔子指针进行处理  

    m[n-1].place =&m[n-2];  

    for(int i=1;i<n-1;i++){  

        if(m[i+1].opp-m[i].opp <m[i].opp -m[i-1].opp ){  

            m[i].place =&m[i+1];  

        }else{  

            m[i].place =&m[i-1];  

        }  

    }  

    for(int i=0;i<n-1;i++){                                              //优先确定“双向奔赴”兔子的末位置  

        if((m[i].place==&m[i+1])&&(m[i+1].place==&m[i])){  

            ans[m[i].index]=ans[m[i+1].index]=(m[i].opp+m[i+1].opp)/2;  

            m[i].u=m[i+1].u=1;  

        }  

    }   

    for(int i=0;i<n;i++){  

        if(m[i].u==0){  

            des(&m[i]);  

        }  

    }  

    for(int i=0;i<n;i++){  

        printf("%d ",ans[i]);  

    }  

    return 0;  

}