软件工程马搏 edited 3 年，9 月前
const int MAX_K = 11;
const int MAX_N = 201;
using namespace std;
typedef struct _Tset {
int order, sum; //记录顺序与总和
double klx; //记录计算得到的KL值
double label[MAX_K]; //以数组记录:基本数据+1/K
}Tset;
int cmp(const void a, const void b) {
if (fabs(((Tset)a)->klx - ((Tset)b)->klx) < 1e-7)
//KL值相等按输入顺序
return ((Tset)a)->order - ((Tset)b)->order < 0 ? -1 : 1;
else
//否则按KL值从小到大
return ((Tset)a)->klx - ((Tset)b)->klx < 0 ? -1 : 1;
}
double KL(Tset x, Tset y, int k) { //输入数组指针及长度k
double kld = 0.0; //初始化KL值
for (int j = 0; jlabel[j] / x->sum *log(x->label[j] / x->sum * y->sum / y->label[j]);
return kld;
}
void solve() / Define function solve() to process one case of the problem /
{
int K, N;
int i, j;
int t;
Tset trials[MAX_N]; //以结构体数组记录所有数据
scanf(“%d %d”, &K, &N); double frac_k = 1.0 / K;
for (i = 0; i <= N; i++) { //包括第一组总共N+1组数据
trials[i].order = i;
trials[i].sum = 1;
for (j = 0; j < K; j++) { //读入并保存每组数据，带1/K
scanf(“%d”, &t); trials[i].label[j] = t + frac_k;
trials[i].sum += t; //记录总和加1 }
trials[i].klx = KL(trials, trials + i, K); //计算KL值并记录
}
}
qsort(trials + 1, N, sizeof(Tset), cmp);
for (i = 1; i <= N; i++)
printf(“%d %.4f\n”, trials[i].order, fabs(trials[i].klx));
}
void init()
{
}
void solve();
int main()
{
int i, t; init();
std::cin >> t;
for (i = 0; i<t; i++)
{
std::cout << “case #” << i << “:” << std::endl;
solve();
}
return 0;
}