程序设计能力实训

1053. KL排序

单点时限: 2.0 sec

内存限制: 256 MB

一个随机变量 可能取 个值。在没有做实验时,我们事先给它的估计是均匀分布 。在做 次随机取值的实验之后,若取某个值 的次数为 ,则该随机变量 的分布记为

对于两个可以取同一组值的随机变量 的 KL 散度表示为:

说明: 是以 为底的对数。

现在有 个随机变量 ,并有它们在多次实验中取每个值的次数。请计算 的 KL 散度值,散度值要求精确到小数点后4位。并根据 的KL散度由小到大对 进行排序。若散度值一样则以输入顺序排序。

输入格式

第 1 行:整数 为测试数据组数。
每组测试数据按照如下格式进行输入:
第 1 行:两个整数 的值, 为随机变量可能的取值个数, 为待排序的随机变量个数。
第 2 行: 个整数,整数取值范围在 之间,表示 在实验中取每个值的次数。
第 3~N+2 行:每行 个整数,整数取值范围在 之间,表示待排序的随机变量 在实验中取每个值的次数。按输入顺序 是每个待排序随机变量的标号。

输出格式

对于每组测试数据,输出一行对应的编号(编号从 0 开始,格式:case #0: 等),然后接下来 行输出排序的结果。每行输出一个整数和一个浮点数,分别是排序后的标号 和对应的随机变量 的 KL 散度值,两个数之间以一个空格分隔,浮点数四舍五入到小数点后 4 位。

样例

Input
3
2 2
1 1
0 5
5 0
2 3
3 3
2 3
6 1
7 7
3 2
2 3 4
5 6 7
7 6 3
Output
case #0:
1 0.5928
2 0.5928
case #1:
3 0.0000
1 0.0141
2 0.2477
case #2:
1 0.0070
2 0.1632

提示

ln是以e为底的对数,C语言提供了标准库函数log计算以e为的对数。
函数原型:double log(double x);
头文件:<math.h>

在计算过程,请进行如下判断:
if(fabs(散度值)<1e-7) 散度值=0.0000;
浮点数的数据类型请定义为 double

对第三组测试数据的解释:

3 2  //K=3,N=2,随机变量可能的取值个数为3,待排序的随机变量个数为 2
2 3 4 //x在实验中取第一个值的次数为2,取第二个值的次数为3, 取第三个值的次数为4,实验次数M=9
5 6 7 //y1在实验中取第一个值的次数为5,取第二个值的次数为6,取第三个值的次数为7,实验次数M=18
7 6 3 //y2在实验中取第一个值的次数为7,取第二个值的次数为6,取第三个值的次数为3,实验次数M=16

不限期开放

题目列表