日々精進

aikoと旅行とプログラミング

【AOJ 1285】Grey Area

問題

Grey Area | Aizu Online Judge

方針

  • ヒストグラムを印刷するために必要なインク量を求めようという問題.
  • vを入力する際に, 区画の最大値(imax), 頻度の最大値(hmax)を求める.
  • hist[i] :=  {i \leq v \leq (i+1)w}の頻度としたとき,  {\sum _{i=0}^{imax} \frac{hist[i]}{hmax} \times \frac{imax-i} {imax}} を計算する.
  • 最後に0.01を足す(線とかを引くためのコストっぽい?)

コード

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)

signed main(){
  int n, w;
  int hist[50];
  int v;
  
  while(cin >> n >> w, n||w){
    int i_max = -1;
    int h_max = -1;
    memset(hist, 0, sizeof(hist));

    REP(i, 0, n){
      cin >> v;
      int idx = (int)(v/w);
      hist[idx]++;
      i_max = max(i_max, idx);
      h_max = max(h_max, hist[idx]);
    }
    
    double ans = 0.0;
    REP(i, 0, i_max+1){
      ans += ((double)hist[i]/h_max)*(double)(i_max-i)/(i_max);
    }
    
    ans += 0.01;
    cout << ans << endl;
  }
}