自动搬运

查看原文

来自洛谷，原作者为

	PR_CYJ 逆水行舟，不进则退

搬运于2025-08-24 22:57:32，当前版本为作者最后更新于2024-05-02 09:06:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

思路

这道题 $1\le n\le 10^6$ 所以显然不是模拟，接下来就考虑数学做法。

我们发现 $w_i=\frac{1}{2}\cdot (a_i+a_{i+1})$，所以 $2\cdot w_i=a_i+a_{i+1}$，然后将 $2\cdot w_i$ 记为 $v_i$，所以 $v_i$ 就是一条边相邻两点的点权和。

接下来就可以用 $a_1$ 表示其它的点。$a_2$ 为 $v_1-a_1$，$a_3$ 为 $v_2-v_1+a_1$。以此类推，当 $n$ 为奇数时，$a_n$ 就是 $v_{n-1}-v_{n-2}+v_{n-3}-v_{n-4}+\cdots +v_2-v_1+a_1$。因为 $a_1$ 与 $a_n$ 的和是 $v_n$，所以 $a_1+v_{n-1}-v_{n-2}+v_{n-3}-v_{n-4}+\cdots +v_2-v_1+a_1=v_n$，即 $2\cdot a_1=v_n-v_{n-1}+v_{n-2}-v_{n-3}+\cdots +v_1$。

接着将右边式子分成两部分，即 $v_n+v_{n-2}+\cdots +v_1$ 和 $-(v_{n-1}+v_{n-3}+\cdots+v_2)$。可以发现，若要使 $a_1$ 最大，就要使 $v_n+v_{n-2}+\cdots +v_1$ 最大，$v_{n-1}+v_{n-3}+\cdots+v_2$ 最小。而 $a_1$ 最小时则相反。

最后只需要将 $w$ 数组排序然后间隔输出即可。

代码

• 切勿抄袭！！！

#include<bits/stdc++.h>
using namespace std;
int n,smnw,bgnw,a[1000010];
int main()
{
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	sort(a+1,a+n+1);
	cout<<a[n/2+1];
	smnw=1;
	bgnw=n/2+2;
	for(int i=2;i<=n;i++)//当a1最大时
		if (i&1)
		{
			cout<<" "<<a[bgnw];
			bgnw++;
		}
		else
		{
			cout<<" "<<a[smnw];
			smnw++;
		}
	cout<<endl<<a[1];
	smnw=2;
	bgnw=n/2+2;
	for(int i=2;i<=n;i++)／／当a1最小时
		if (i&1)
		{
			cout<<" "<<a[smnw];
			smnw++;
		}
		else
		{
			cout<<" "<<a[bgnw];
			bgnw++;
		}
}