最初無駄に探索してしまったけど不要だった。
http://community.topcoder.com/stat?c=problem_statement&pm=13880
問題
N匹のキツネがおり、それぞれの身長はH[i]である。
これらを円形に(任意の順で)並べたとき、隣接したキツネの身長差の最大値をDとする。
Dが最小となるようなキツネの並び方の一例を求めよ。
解法
Hが昇順にソートされていたとする。
H[0]-H[2]-H[4]-...-H[N-1]-...H[5]-H[3]-H[1]と元の数列で添え字が2個離れた要素を順につないでいけばよい。
class FoxesOfTheRoundTable { public: vector <int> minimalDifference(vector <int> h) { int N=h.size(),i,j; pair<int,int> P[1010]; FOR(i,N) P[i]={h[i],i}; sort(P,P+N); int l=0,r=N-1; vector<int> R(N,0); FOR(i,N) { if(i%2==0) R[l++]=P[i].second; else R[r--]=P[i].second; } return R; } }
まとめ
最初はDを探索して、差がD未満のものを連結して輪を作れるか試したりしていた。
それでもAC出来るけどだいぶ時間食っちゃったね。