TopCoder SRM244 I 300 - CircleDance
题目大意：
已知n个人的身高（3<=n<=20），要求他们围成一个圈，使得相邻两人最大的身高之差最小。
原文：
Given a group of dancers' heights, arrange a circle formation that minimizes the maximum height difference between each pair of neighboring dancers.
Write a class CircleDance with a method arrangeDancers that takes a int[], heights, and returns the maximum height difference between neighboring dancers.
解题思路：-------------------------------------------------------------------------------------------------------------
数据规模相当小，可以考虑使用枚举。但仔细考虑，可以有一种直接构造的方法得到最优方案。
当只有3个人的情况，围成一圈，最大的高度差为最高和最矮之差。因为他们无可避免地要站在相邻的位置。假设a<b<c，那么此时max=c-a。
若再插入一个d > a,b,c，那么d必然和2个人相邻。若把d安排和a相邻，显然是不合适的，因为这样必然会使max增加到max=d-a。所以，此时的d放在bc之间是最优选择，那么d两侧的最大高度差为d-b，即使d-b比原来的max更大也是无可奈何的。
同样地，若再插入一个e > a,b,c,d，那么e必然是放在当前最高的两人之间，即cd之间。依此类推。按照这样的规则，就可以依次插入一个更高的人，使他们构成一个环形，并且他们相邻两人的高度差的最大值是最小的。虽然没有严格证明（哪位朋友若有证明请吱一声^^）。
那么这个题就能解决了，先把人按照高度排序，编号奇数的由低到高站左边，偶数的由高到低站右边，然后首尾相接即可。
附代码：------------------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#define N 25
using namespace std;
class CircleDance
{
public:
int abs(int x)
{
return x>0?x:-x;
}
int Max(int a,int b)
{
return a>b?a:b;
}
int arrangeDancers(vector <int> h)
{
int i,j,k,n;
int max,t,g[N];
n=h.size();
//sort
for(i=0;i<n;i++)
{
k=i;
for(j=i+1;j<n;j++) if(h[k]>h[j]) k=j;
t=h[k];h[k]=h[i];h[i]=t;
}
//range
k=0;
for(i=0;i<n;i+=2) g[k++]=h[i];
for(i=n%2?n-1:n-2;i>0;i-=2) g[k++]=h[i];
//getmax
max=abs(g[k-1]-g[0]);
for(i=1;i<k;i++) max=Max(max,abs(g[i]-g[i-1]));
return max;
}
};
int main() //test
{
vector <int> h;
int i,j,k,n;
int max;
CircleDance c;
while(scanf("%d",&n),n)
{
for(i=0;i<n;i++){
scanf("%d",&k);
h.push_back(k);
}
max=c.arrangeDancers(h);
h.clear();
printf("%d/n",max);
}
return 0;
}