练习题 - 合并果子(贪心+堆排序)

前言

算法拾遗继续。

题目

问题描述

在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 
每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过n-1次合并之后,就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 
因为还要花大力气把这些果子搬回家,所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使多多耗费的体力最少,并输出这个最小的体力耗费值。 
例如有3种果子,数目依次为1,2,9。可以先将1、2堆合并,新堆数目为3,耗费体力为3。接着,将新堆与原先的第三堆合并,又得到新的堆,数目为12,耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。

输入(fruit.in)

输入文件fruit.in包括两行,第一行是一个整数n(1<=n<=10000),表示果子的种类数。第二行包含n个整数,用空格分隔,第i个整数ai(1<=ai<=20000)是第i种果子的数目。

输出(fruit.out)

输出文件fruit.out包括一行,这一行只包含一个整数,也就是最小的体力耗费值。输入数据保证这个值小于231。

样例

fruit.in

3 
1 2 9

fruit.out

15

数据规模

对于30%的数据,保证有n<=1000: 
对于50%的数据,保证有n<=5000; 
对于全部的数据,保证有n<=10000。

解答

本题可采用贪心算法求解,也即每次优先合并果子数目最小的两堆水果。另外,本题涉及到每次取果子堆中数目最少的堆,已经加入合并后的果子堆。这种取最小值并需要插入新值且要维护顺序的任务特别适合采用堆排序算法。因此,本题考查点为贪心算法+堆排序算法。

具体代码实现如下。

#include <stdio.h>

FILE *in, *out;
int n, a[10001];

void deal(int k) {
  int flag = k, exchange;

  if (2 * k <= n && a[2 * k] < a[flag])
    flag = 2 * k;

  if (2 * k + 1 <= n && a[2 * k + 1] < a[flag])
    flag = 2 * k + 1;

  // move the smaller into first half of array a[] 
  if (flag != k) {
    exchange = a[flag];
    a[flag] = a[k];
    a[k] = exchange;

    deal(flag);
  }
}

void creat() {
  int i;
  for (i = n / 2; i > 0; i--)
    deal(i);
}

int pop() { // returns the smallest number in array a[]
  int ret = a[1];
  a[1] = a[n--];

  deal(1);
  return (ret);
}

void add(int num) {
  int flag;

  a[++n] = num;
  flag = n;

  while (flag > 1) {
    if (a[flag / 2] > num) {
      a[flag] = a[flag / 2];
      a[flag / 2] = num;
      flag /= 2;
    } else {
      break;
    }
  }
}

int main() {
  int i, x = 0, y = 0, sum = 0;

  in = fopen("fruit.in", "r");
  fscanf(in, "%d", &n);
  for (i = 1; i <= n; i++)
    fscanf(in, "%d", &a[i]);
  fclose(in);

  creat(); // build a binary minimum heap

  while (n > 1) {
    x = pop();
    y = pop();
    sum += x + y;
    add(x + y);
  }

  out = fopen("fruit.out", "w");
  fprintf(out, "%d\n", sum);
  fclose(out);

  return 0;
}

参考


* cached version, generated at 2018-12-04 09:44:21 UTC.

Subscribe by RSS