科學(xué)家發(fā)明了一種新的生物，這種生物能夠兩兩合并，重量為m1的生物與重量為m2的生物合并后變?yōu)橐粋€(gè)生物，該生物的重量為2*sqrt(m1*m2)。求給定數(shù)量的生物合并成一個(gè)生物后的最小重量。
貪心算法，每次選取重量最大的兩個(gè)生物合并成一個(gè)即可。下面的代碼是有優(yōu)先隊(duì)列（大頂堆）實(shí)現(xiàn)的。
不過，深入分析一下，由數(shù)學(xué)公式可以證明：m1+m2 >= 2*sqrt(m1*m2)，因此當(dāng)兩個(gè)生物合并后，重量一定是剩余生物中最大的，由此只要將原重量按降序排序一次，然后依次合并即可。
優(yōu)先隊(duì)列有些大材小用了。
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define LEN 110
void f(double *a, int top, int r)
{//篩選函數(shù)，保持大頂堆的性質(zhì)。
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--)//建立大頂堆，即是初始化隊(duì)列
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]);
}
}