科学家发明了一种新的生物，这种生物能够两两合并，重量为m1的生物与重量为m2的生物合并后变为一个生物，该生物的重量为2*sqrt(m1*m2)。求给定数量的生物合并成一个生物后的最小重量。
贪心算法，每次选取重量最大的两个生物合并成一个即可。下面的代码是有优先队列（大顶堆）实现的。
不过，深入分析一下，由数学公式可以证明：m1+m2 >= 2*sqrt(m1*m2)，因此当两个生物合并后，重量一定是剩余生物中最大的，由此只要将原重量按降序排序一次，然后依次合并即可。
优先队列有些大材小用了。
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define LEN 110
void f(double *a, int top, int r)
{//筛选函数，保持大顶堆的性质。
int i, j;
for(j = 2 * top; j <= r; j *= 2)
{
if(j < r && a[j] < a[j + 1])
j++;
if(a[j] <= a[j / 2])
break;
double t = a[j];
a[j] = a[j / 2];
a[j / 2] = t;
}
}
double DeQueue(double *a, int *r)
{
double t = a[1];
a[1] = a[*r];
--*r;
f(a, 1, *r);
return t;
}
void EnQueue(double *a, int *r, double num)
{
++*r;
a[*r] = num;
int i = *r;
while(1)
{
if(i > 1 && a[i] > a[i / 2])
{
double t = a[i];
a[i] = a[i / 2];
a[i / 2] = t;
i /= 2;
}
else
break;
}
}
int main()
{
int i, j;
int N;
int r;
double a[LEN];
double w;
while(scanf("%d", &N) != EOF)
{
for(i = 1; i <= N; i++)
scanf("%lf", &a[i]);
for(i = N / 2; i >= 1; i--)//建立大顶堆，即是初始化队列
f(a, i, N);
r = N;
while(r > 1)
{
double m1 = DeQueue(a, &r);
double m2 = DeQueue(a, &r);
w = 2.0 * sqrt(m1 * m2);
EnQueue(a, &r, w);
}
printf("%.3lf\n", a[1]);
}
}
posted on 2012-07-21 22:22
小鼠标 阅读(767)
评论(0) 编辑 收藏 引用 所属分类:
排序 、
数据结构