Hdu 4153 & COJ 1530 Grey Area
仔细观察可以看为：3/3*5/5+2/3*3/5+1/3*1/5+0/3*1/5+0.01
又题目的最后一组测试数据是：
10 10
1
2
3
4
5
16
17
18
29
30
这可以得出什么结论呢？
（1）首先看3，3是怎么来的？看测试数据中最大的测试数据为30，而它的w值为10，所以3是由最大的测试数据与w相除得到的，即3 = 30/10；然后3/3, 2/3, 1/3, 0/3逐级递减。
（2）观察可得5/5,3/5,1/5,1/5。我们来看，5怎么得到的呢？在直方图中出现最多的那个数就是5.而5,3,1,1则是各自在直方图中出现的频率。
由此可得结果，最后保留6位小数。
CODE:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
const int SIZE = 1001;
int value[SIZE];
int hash[SIZE]; //hash
int n, w;
void init()
{
memset(value, 0, sizeof(value));
memset(hash, 0, sizeof(hash));
}
int cmp(const void *a, const void *b)
{
return *(int*)a - *(int*)b;
}
int main()
{
int i, j;
double s;
while(~scanf("%d%d",&n, &w), n, w)
{
s = 0.01;
init();
for(i = 0; i < n; i++)
{
scanf("%d", &value[i]);
}
qsort(value, n, sizeof(int), cmp);
int max = value[n-1]/w;
for(i = 0; i < n; i++)
{
int k = value[i]/w;
hash[k]++;
}
int div = -1;
for(i = 0; i <= max; i++)
{
if(hash[i] > div)
{
div = hash[i];
}
}
for(i = max;i >= 0; i--)
{
s += 1.0*i/max*hash[max-i]/div;
}
printf("%.6lf\n", s);
}
return 0;
#include <string.h>
#include <stdlib.h>
using namespace std;
const int SIZE = 1001;
int value[SIZE];
int hash[SIZE]; //hash
int n, w;
void init()
{
memset(value, 0, sizeof(value));
memset(hash, 0, sizeof(hash));
}
int cmp(const void *a, const void *b)
{
return *(int*)a - *(int*)b;
}
int main()
{
int i, j;
double s;
while(~scanf("%d%d",&n, &w), n, w)
{
s = 0.01;
init();
for(i = 0; i < n; i++)
{
scanf("%d", &value[i]);
}
qsort(value, n, sizeof(int), cmp);
int max = value[n-1]/w;
for(i = 0; i < n; i++)
{
int k = value[i]/w;
hash[k]++;
}
int div = -1;
for(i = 0; i <= max; i++)
{
if(hash[i] > div)
{
div = hash[i];
}
}
for(i = max;i >= 0; i--)
{
s += 1.0*i/max*hash[max-i]/div;
}
printf("%.6lf\n", s);
}
return 0;
}
转载于:https://www.cnblogs.com/g0feng/archive/2012/08/22/2651479.html