题解 3298: 蓝桥杯2024年第十五届决赛真题-兔子集结

解题思路:兔子可以分为双向奔赴的兔子和单相思兔子，双向奔赴的兔子最终位置为两个兔子初始位置之和除以2并向下取整 ，单相思兔子最终位置就等于移动方向的第一只双向奔赴的兔子的位置 

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

struct rabbit{

long long l;//存储位置 

long long n;//存储编号 

}; 

bool cmp1(rabbit a,rabbit b){

return a.l<b.l;

}

bool cmp2(rabbit a,rabbit b){

return a.n<b.n;

}

int main(){

long long N;

cin>>N;//记录兔子数量 

vector<rabbit>r(N);

for(long long i=0;i<N;i++){

    cin>>r[i].l;//记录兔子位置 

    r[i].n=i;

}

sort(r.begin(),r.end(),cmp1);//根据位置大小排序 

vector<long long>d(N+1);//记录兔子同伴的方向 

d[0]=1;//第一个和最后一个兔子单独处理 

d[N-1]=-1; 

for(long long i=1;i<N-1;i++){

    if((r[i].l-r[i-1].l)<=(r[i+1].l-r[i].l)){//等于号便可完成两边距离相等选左边 

        d[i]=-1;//左边距离近就把d[i]记为-1表示同伴在左边 

    }

    else{

        d[i]=1;

    }

}

d[N]=99;//多取一个值是因为下面的判断会查询d[N]的值，设置一个无关数既不影响判断也不会超限 

for(long long i=0;i<N;i++){

    if(d[i]==1&&d[i+1]==-1){//双向奔赴的兔子的处理 

        r[i].l=r[i+1].l=(r[i].l+r[i+1].l)/2;//最终位置为两个兔子初始位置之和除以2并向下取整 

    }

}

for(long long i=0;i<N;i++){

    if(i==0) {//这里要把0单独拿出来，因为下面的判断中会存在d[i-1],i=0会发生超限 

        if(!(d[i+1]==-1)){//d[0]一定为1，所以判断条件也可以简化 

            long long k=i+d[i];

            while(!(d[k]==d[i]&&d[k+d[i]]==-d[k])){

                k=k+d[i];

                }

        r[i].l=r[k].l;

            }

    }else{

            if(!((d[i]==1&&d[i+1]==-1)||d[i]==-1&&d[i-1]==1)){//非双向奔赴即单相思兔子的处理 

            long long k=i+d[i];

            while(!(d[k]==d[i]&&d[k+d[i]]==-d[k])){//这一步是不断在找该单相思兔子移动方向的第一只双向奔赴的兔子 

                    k=k+d[i];

                }

        r[i].l=r[k].l;//单相思兔子最终位置就等于移动方向的第一只双向奔赴的兔子的位置 

            }

        }

}

sort(r.begin(),r.end(),cmp2);//根据编号排序 

for(long long i=0;i<N;i++){//输出最终位置信息 

cout<<r[i].l<<" ";

}

return 0;

}