足跡-sokuseki-

りかの日進月歩の記録

AOJ1285 Grey Area

Grey Area | Aizu Online Judge

問題概要

 N 個のデータからヒストグラムを作ります。
それぞれのヒストグラムの棒の幅は w で、棒の高さは、ヒストグラムの棒の長さの最大値を1としたときの割合で定義されます。
ヒストグラムの棒はそれぞれ色の濃さが異なり、ヒストグラムの棒がk本あったとき、左からi本目の濃さは \frac{k-i}{k-1} です。
あなたはヒストグラムを作る際の必要なインクの量が知りたいです。
ここで必要なインクの量は、「 0.01 + \sum_{i = 1}^{k} i 本目のヒストグラムの棒の高さ* i 本目のヒストグラムの棒の色の濃さ」です。
誤差は 10^{-5} まで許容されます。

制約

 1 \le n \le 100
 10 \le w \le 50
 0 \le v_i \le 100

解法

棒の幅は  w なので、 v_i は左から \lfloor \frac{v_i}{w} \rfloor 番目の棒の要素になります。( v_i が小さいので、何番目の棒かを \frac{v_i}{w} 回試しても間に合います)
それぞれの棒の度数(長さ)を求めてから、それぞれの棒のインクの量を足し合わせてあげると良いです。
計算量は  O(N) でできます。


AIZU ONLINE JUDGE: Code Review