P10393 无限循环？题解

题意

有一个 $n$ 个节点的环（$n$ 是奇数），每个点 $i$ 有点权 $a_i$，现在已知了边权 $w_i=\dfrac{1}{2}(a_i+a_{i+1})$，其中 $w_n=\dfrac{1}{2}(a_1+a_n)$，这个权值和可以任意对应，改变边权时 $a_i$ 会自动调整，现在要求出两种边权的对应方法，分别使得 $a_1$ 取得最大值和最小值。

思路

我们尝试把 $a_1$ 表示一下（因为要求它的最值）。

易得方程组：
$$
\begin{equation*}
\begin{cases}
a_1+a_2=2w_1\
a_2+a_3=2w_2\
\cdots\
a_{n-1}+a_n=2w_{n-1}\
a_n+a_1=2w_n
\end{cases}
\end{equation*}
$$
题目中的 $n$ 为奇数刚好帮我们避免了分类讨论。

现在求 $a_1$，将所有方程加起来左右同时除以 $2$ 得：
$$
a_1+a_2+\cdots+a_n=w_1+w_2+\cdots+w_n
$$
减掉不需要的项：
$$
\begin{align}
a_1
&=a_1+a_2+\cdots+a_n-(a_2+a_3)-(a_4+a_5)-\cdots-(a_{n-1}+a_n)\
&=w_1+w_2+\cdots+w_n-(2w_2+2w_4+\cdots+2w_{n-1})
\end{align}
$$
要求 $a_1$ 最大值，就要使得 $(2w_2+2w_4+\cdots+2w_{n-1})$ 最小，也就是使得 $(w_2+w_4+\cdots+w_{n-1})$ 最小。

也就是把较小的 $w$ 值放在偶数位置上面。

最小值同理，就是把把较大的 $w$ 值放在偶数位置上面。

于是做完了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include<bits/stdc++.h>
using namespace std;
int n,a[1000001];
bool cmp(int aa,int bb){
    return aa>bb;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
        if(i%2)cout<<a[n/2+1+i/2]<<" ";
        else cout<<a[i/2]<<" ";
    cout<<endl;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
        if(i%2)cout<<a[n/2+1+i/2]<<" ";
        else cout<<a[i/2]<<" ";
    cout<<endl;
    return 0;
}