AOJ 1285 - Grey Area

問題概要

n個の数値v₁,v₂,…,v_nとwが与えられる。
1区間の範囲をwにしたヒストグラムを作成する。例えば、下図ならば、w = 10で各区間は、0~9,10~19,20~29,30~39のようになる。この各区間の棒グラフに色を塗る。一番左を黒に、それから右に行く毎に色を薄くしていき、一番右を白に塗る。このとき、色を塗るために使用したインクの使用量を求めよ。このヒストグラムの縦軸は各区間に含まれる値の総数を表す。

制約

• 1 ≤ n ≤ 100
• 10 ≤ w ≤ 50
• 0 ≤ v_i ≤ 100

解法

まず、各区間の総数を求め、それをp[i]とする。v_i/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;
}