庆祝六一

╰+攻爆jí腚メ 2022-06-13 08:53 165阅读 0赞

**题目：**

**牛家庄幼儿园为庆祝61儿童节举办庆祝活动,庆祝活动中有一个节目是小朋友们围成一个圆圈跳舞。牛老师挑选出n个小朋友参与跳舞节目,已知每个小朋友的身高h\_i。为了让舞蹈看起来和谐,牛老师需要让跳舞的圆圈队形中相邻小朋友的身高差的最大值最小,牛老师犯了难,希望你能帮帮他。**

**如样例所示:  
当圆圈队伍按照100,98,103,105顺时针排列的时候最大身高差为5,其他排列不会得到更优的解。 **

##### 输入描述: #####

输入包括两行,第一行为一个正整数n(3 ≤ n ≤ 20) 第二行为n个整数h_i(80 ≤ h_i ≤ 140),表示每个小朋友的身高。

##### 输出描述: #####

输出一个整数,表示满足条件下的相邻小朋友身高差的最大值。

**示例1**

## 输入 ##

## 4 ##

## 100 103 98 105 ##

## 输出 ##

**5**

**分析：对于给定的序列：1、3、5、4、7、6、2，假设是此序列已经是按升序排好的：1、2、3、4、5、6、7。**

**       序号位置间隔越小其差值越小 ，要想整体两两间隔最小，可以将有序的序列从头到尾分别按****左右顺序****插入到一个新的序列中，这样形成一种金字塔型。假设一个与原序列大小相同的序列b，过程如下：**

**                a：  1    2    3    4    5    6    7 **

**                b：**

**           下标：  0    1    2    3    4    5    6 **

**第一次插入：  ** 1                                  2

**第二次插入：  1    **3                      4 **   2**

**第三次插入：  1    3    **5          6 **   4    2**

**第四次插入：  1    3    **5     **7**   6 **   4    2**

**最终b序列为：1    3    5     7   6    4    2**

最后我们将b序列从第二个位置开始向后遍历，判断当前位置和其前面一个位置的差值，注意题目是要围成一个圈，所以最后还需要判断最后一个位置和第一个位置的差值。差值最大的值即为所求的值。参考代码如下：

#include<iostream>
    #include<algorithm>
    using namespace std;
    int main()
      {
         int n;
         while(cin>>n)
         {
           int a[n];
           int b[n];
           for(int i=0;i<n;i++)
              cin>>a[i];
           sort(a,a+n);
           int j=0; 
           int k=n-1;
           for(int i=0;i<n;i++)
             {
                if(i%2==0)
                  { 
                    b[j]=a[i];
                    j++;
                  }
               else
                  {
                    b[k]=a[i];
                    k--;
                  }
             }
           int maxHeiRes=abs(b[1]-b[0]); //注意要加绝对值，因为数组b前向后之差可能为负值
           for(int i=2;i<n;i++)
            {
              int temp=abs(b[i]-b[i-1]);
              if(temp>maxHeiRes)
                  maxHeiRes=temp;
            }
           int temp1=abs(b[n-1]-b[0]);
           if(maxHeiRes<temp1)
              maxHeiRes=temp1;
           cout<<maxHeiRes<<endl;
         }
      }