P10393题解

· · 题解

题目传送门

思路

这道题 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++;
        }
}