11497 통나무 건너뛰기

https://www.acmicpc.net/problem/11497

인접한 통나무의 높이의 차가 최소가 되려면 어떻게 해야 할까? 처음에는 정렬하는 방법을 생각했다. 그러나 통나무가 원형으로 연결되어 있으므로 정렬할 경우 맨 앞과 맨 뒤의 차이가 최대가 되어버려서 최악의 경우가 된다. 일단 정렬을 한 후 차례대로 앞, 뒤에 쌓아가면서 정규분포처럼 만들면 높이의 차를 최소로 만들 수 있다.

#include <cstdio>
#include <algorithm>
using namespace std;
 
int t,n,f,r,a[10000],b[10001],ans;
 
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        sort(a,a+n);
        f=0,r=n-1;
        for(int i=0;i<n;i++)
        {
            if(i%2==0) b[f++]=a[i];
            else b[r--]=a[i];
        }
        b[n]=b[0],ans=0;
        for(int i=0;i<n;i++)
            ans=max(ans,abs(b[i]-b[i+1]));
        printf("%d\n",ans);
    }
    return 0;
}