科學家發明了一種新的生物，這種生物能夠兩兩合并，重量為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
小鼠標 閱讀(805)
評論(0) 編輯 收藏 引用 所屬分類:
排序 、
數據結構