TopCoder SRM 554 Div1 Medium TheBrickTowerMediumDivOne

こういう問題は割と好き。
http://community.topcoder.com/stat?c=problem_statement&pm=12161

問題

N個のブロックがあり、その高さはH[i]である。
このブロックを1列に並べたい。
ブロックの並び順は元の順と買えても良い。

ここで、ブロックが1個倒れても他のブロックにぶつからないよう互いに距離を置きたい。
例えばi番目のブロックの位置X[i]とj番目のブロックの位置X[j]はmax(H[i],H[j])以上離れていなければならない。

先頭から末尾のブロックの距離が最小となる並べ方のうち、並べ方のindex数列が辞書順最小となるものを答えよ。

解法

まず辞書順は置いておいて距離の最小化を考える。
一連のブロックのうち最高の高さH[x]のブロックxがある場合、それを列の真ん中に入れてしまうと、その前と後ろにそれぞれH[x]距離を空けないと行けないので、距離が2*H[x]伸びてしまう。
よって高いブロックは先頭か末尾に置けば、距離が伸びるのはH[x]だけで済む。

後は辞書順を考慮した並べ方を考える。
残されたブロック群のうち先頭または末尾に置くブロックを1つずつ選択していく。

最高の高さのブロックが残されたブロックの先頭にあるなら、そのブロックは先頭に残していくとindexが辞書順最小になる。
それ以外の場合、最高の高さのブロックは末尾に持っていくのが良い。同じ高さのブロックが複数ある場合は、一番後ろにあるブロックを末尾に持っていくと良い。

class TheBrickTowerMediumDivOne {
	public:
	int N;
	vector<int> org,res;
	
	void solve(vector <int> index) {
		int i,ind=0,v;
		
		if(index.empty()) return;
		
		ind=0;
		FOR(i,index.size()) if(org[index[ind]] <= org[index[i]]) ind=i;
		
		if(org[index[ind]] == org[index[0]]) ind=0;
		
		v = index[ind];
		index.erase(index.begin()+ind);
		
		if(ind==0) {
			res.push_back(v);
			solve(index);
		}
		else {
			solve(index);
			res.push_back(v);
		}
	}
	
	vector <int> find(vector <int> heights) {
		int i,j,v,minc;
		vector<int> index;

		org = heights;
		N=heights.size();
		res.clear();
		
		FOR(i,N) index.push_back(i);
		
		solve(index);
		
		return res;
	}
}

まとめ

辞書順周りの処理が若干難しい。