SRM554 Div1 500

問題

N本のブロックのタワーがあり、0からN-1の番号が振られており、それぞれの高さheightsが与えられる。
このタワーを横一列に並べる。
このとき、あるタワーが倒れても横のタワーが倒れないように、2つのタワー間の距離は、その2つのタワーの高いほうの高さと少なくとも同じにしなければいけない。
最初のタワーと最後のタワーの間の距離が最小になるようにしたい。

そうなるように、i番目に立てるべきタワーのナンバーを要素に持つ配列を返す。
もし距離が最小になるようなものが複数ある場合は、辞書順最小を返せ。

配列Aが配列Bより辞書順で最小とは、最初に要素が異なるiを比べたときに、A[i]

考え方

距離が最適(最小)になるものは、実験してみるといくつもあることがわかる。
たとえば、インデクスを無視すると、{4,5,7}の場合は、4,5,7のほかに5,4,7も7,5,4も同じ距離になる。

ここで気づかないといけないのは、「一番高さが小さいものから左右に向かってどんどん大きくなるようにすれば最適になる」、ということ。

すると、そうなるようにうまくインデクスを配置していけばよい。
これはgreedyで実現できる。

与えられたタワーを高さが低いものから配置していく。
一番小さいタワーはそのまま置く。
次に、小さいタワーを左右どちらかに置くことを考える。
もし、一番小さいタワーのインデクスより小さければ左側、大きければ右側に置かないといけない。
これを繰り返していく。
すでに置かれたタワーがすべて最適に設置されているとすると、置いてあるタワーの中で一番インデクスが小さいものより小さいインデクスを配置する場合は左側、大きいインデクスを配置する場合は右側に置く。

同じ高さのものが複数あった場合、左側に置くときは、左側に置かれるインデクスの中で一番大きいもの、右側に置くときは、右側に置かれるインデクスの中で一番小さいものを選ぶ必要がある。