P10393 无限循环？题解

1. 题意

   有一个 $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$ 取得最大值和最小值。

2. 思路

   我们尝试把 $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$ 值放在偶数位置上面。

   于是做完了。

3. 代码

   #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;
   }