kmjp's blog

競技プログラミング参加記です

TopCoder SRM 662 Div1 Easy FoxesOfTheRoundTable

最初無駄に探索してしまったけど不要だった。
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出来るけどだいぶ時間食っちゃったね。