AOJ 1285 - Grey Area
問題概要
n個の数値v1,v2,…,vnとwが与えられる。
1区間の範囲をwにしたヒストグラムを作成する。例えば、下図ならば、w = 10で各区間は、0~9,10~19,20~29,30~39のようになる。この各区間の棒グラフに色を塗る。一番左を黒に、それから右に行く毎に色を薄くしていき、一番右を白に塗る。このとき、色を塗るために使用したインクの使用量を求めよ。このヒストグラムの縦軸は各区間に含まれる値の総数を表す。
制約
- 1 ≤ n ≤ 100
- 10 ≤ w ≤ 50
- 0 ≤ vi ≤ 100
解法
まず、各区間の総数を求め、それをp[i]とする。vi/wでどこの区間に含まれるかがわかる。上図だと、p[0] = 5, p[1] = 3, p[2] = 1, p[3] = 1のようになる。
区間の個数-1をNとする。上図だと、N = 3 (0~9,10~19,20~29,30~39で区間の個数は4個であり、それ-1なので3)。
区間の総数の最大値をdとする。上図だと、0~9は5,10~19は3,20~29は1,30~39は1なのでその最大値は5であるのでd = 5とする。
後は、
に当てはめて、最後にansに0.01を足すと答えになる。
ちなみにこの0.01は塗りつぶし以外(枠線など)に使用するインクの量。
感想
英語読解がかなり難しい。とにかく読めない。
コード
#include <bits/stdc++.h> using namespace std; int main(){ int n,w,v; while(cin >> n >> w, n){ int N = 0; double p[11] = {0}; for(int i = 0 ; i < n ; i++){ cin >> v; p[v/w]++; N = max(N,v/w); } double d = *max_element(p,p+11),ans = 0; for(int i = 0 ; i < N ; i++){ ans += (p[i]/d)*((double)(N-i)/N); } printf("%f\n",ans+0.01); } return 0; }