SRM554 Div2 Medium "TheBrickTowerMediumDivTwo"

問題

高さがいろいろな塔を一列に並べる。
ただし、隣り合う塔は高いほうの塔の高さだけ、距離をとる必要がある。

塔の高さheightsが与えられるので、
距離がなるべくとらないような置き方を返せ。
そのような置き方が複数ある場合、辞書順で一番小さいものを返せ。

制約

1 <= 塔の高さ <= 7
1 <= 塔の数 <= 47

考えた事

とりあえず、4, 7, 5みたいに山なりに塔を配置しちゃうとだめだ
列で山なりの部分がなければ距離は最低にできる
→5, 3, 2, 4, 7みたいた谷の形とか降順昇順問わずソートされてる列だったらなんでもいい
最初は絶対インデックス０を選んでインデックス重視でだんだん小さく、
もう小さいのがなくなったら今度はだんだん大きくしてけばいっか

ソース

class TheBrickTowerMediumDivTwo {
public:
	vector <int> find(vector <int> heights){

		const int MAX_N = 47;
		bool use[MAX_N];
		memset( use, false, sizeof(use) );

		int n = heights.size();

		vector<int> res;
		res.push_back(0);
		use[0] = true;
		int h = heights[0];
		// だんだん小さくなるように選んでいく
		while( true ){
			bool update = false;
			for( int i = 1; i < n; i++ ){
				if( use[i] )  continue;
				if( heights[i] <= h ){
					use[i] = true;
					res.push_back(i);
					h = heights[i];
					update = true;
				}
			}
			if( !update ) break;
		}

		// あとはだんだん大きくなるようにに選んでいく
		int r = heights.size() - res.size();
		for( int i = 0; i < r; i++ ){
			int mv = 9999;
			int mi = -1;
			for( int j = 0; j < n; j++ ){
				if( use[j] ) continue;
				if( mv > heights[j] ){
					mv = heights[j];
					mi = j;
				}
			}
			res.push_back(mi);
			use[mi] = true;
		}

		return res;
	}
};