自动搬运

查看原文

来自洛谷，原作者为

	_xzhdsnh1364 fw蒟蒻|壶关（请私信）：/paste/6gnbzgic|一年后改名Linear_allogue|无钩六不改签|已禁言

搬运于2025-08-24 21:17:45，当前版本为作者最后更新于2025-03-09 17:16:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题外话

一个星期第二篇题解。

题意

$n$ 个同学围成一个环，要使相邻两人身高差距最大值最小，求排序后身高的序列。

解法

看完题目，很多童鞋可能会认为，直接从小到大排序就好了呀，可是这是一个环，所以我们要从小到大按身高将每个同学均匀分布在两侧。还有一种情况，就是同学数量为奇数，那也简单，将最终序列最后一个同学设为身高排序序列在最中间的那个同学就好了。

还有此题数据输入量最高可到达 $5 \times 10 ^ 6$，所以记得关闭流同步或加上快读。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5e6 + 5;
int n , a[N] , ans[N] , now = 1 , l , r;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    r = n;
    for(int i = 1;i <= n;i++)cin >> a[i];
    sort(a + 1 , a + n + 1);
    for(int i = 1;i <= n;i += 2){
        ans[++l] = a[i];
        ans[r--] = a[i + 1];
    }
    if(n % 2 == 1)ans[l] = a[n];
    for(int i = 1;i <= n;i++)cout << ans[i] << ' ';
    return 0;
}