AOJ1285 Grey Area
問題概要
個のデータからヒストグラムを作ります。
それぞれのヒストグラムの棒の幅は で、棒の高さは、ヒストグラムの棒の長さの最大値を1としたときの割合で定義されます。
ヒストグラムの棒はそれぞれ色の濃さが異なり、ヒストグラムの棒がk本あったとき、左からi本目の濃さはです。
あなたはヒストグラムを作る際の必要なインクの量が知りたいです。
ここで必要なインクの量は、「本目のヒストグラムの棒の高さ* 本目のヒストグラムの棒の色の濃さ」です。
誤差は まで許容されます。
制約
解法
棒の幅は なので、 は左から 番目の棒の要素になります。( が小さいので、何番目の棒かを 回試しても間に合います)
それぞれの棒の度数(長さ)を求めてから、それぞれの棒のインクの量を足し合わせてあげると良いです。
計算量は でできます。