TopCoder SRM 346 Div1 Medium HeightRound

問題

n人の人がいて、それぞれの人の背の高さはheights[i]である。
このn人が円上に並ぶ。

隣り合う人同士の背の高さの差の絶対値の最大値を最小にしたい。
そのような並び順を出力せよ。
複数あるときは、辞書順で最も最初に来るものを出力せよ。

制約条件

n≦50
heights[i]≦1000

方針

円形に並べるので、最初の一人は一番背の低い人で固定でよい。
残りの部分について、差の絶対値の最大値をdとして、
d以下で人を並べられるかについて二分探索する。

人を並べられるかは、差がd以下の人のうち、最も大きい人を貪欲に使っていって、
最後に最初の一人とつながったときにその差がd以下ならよい。

dが求まったら、先頭から一人ずつ試していき、
上と同様の判定方法で、並び順があるかを見る。
並び順があったら、その人を使ってよい。

ソースコード

bool can(int d,vi &h,int s){
	sort(h.begin()+s,h.end());
	int n=h.size(), l=h[s-1];
	bool use[50]={};
	
	for(int i=s;i<n;i++){
		for(int j=n-1;j>=s;j--)if(!use[j]&&abs(h[j]-l)<=d){
			use[j]=1; l=h[j];
			goto NEXT;
		}
		return 0;
		NEXT:;
	}
	return abs(h[0]-l)<=d;
}

class HeightRound {
	public:
	vector <int> getBestRound(vector <int> heights) 
	{
		sort(all(heights));
		int n=heights.size();
		int lo=-1,hi=1000,mid;
		while(lo+1<hi){
			mid=(lo+hi)/2;
			if(can(mid,heights,1))hi=mid; else lo=mid;
		}
		vi ans;
		ans.pb(heights[0]);
		rep(i,n-1){
			for(int j=i+1;j<n;j++){
				swap(heights[j],heights[i+1]);
				if(can(hi,heights,i+2)){
					ans.pb(heights[i+1]);
					break;
				}
				swap(heights[j],heights[i+1]);
			}
		}
		
		return ans;
	}
};