13. 郭老师爱合并果子

1 题目描述

郭老师爱合并果子

成绩	20	开启时间	2021年10月8日 星期五 18:00
折扣	0.8	折扣时间	2021年10月26日 星期二 00:00
允许迟交	否	关闭时间	2021年12月1日 星期三 00:00

郭老师家有个果园，每年到了秋收的时候都会收获很多不同种类的果子。他决定把所有的果子合成一堆，但由于体力有限，郭老师在每次合并的时候只能将两堆果子合并到一起。假设有 ​ 堆果子，那么经过 ​ 次合并即可完成任务，且消耗的总体力等于每次合并所消耗的体力之和。

因为郭老师还需要保留体力将果子运回家，所以在合并果子过程中要尽可能地节省体力。假定每个果子重量均为​，并且已知果子的种类数和每种果子的数目，你的任务是设计出合理的合并方案，使郭老师耗费的体力最少。

例如有​种果子，数目依次为​。合并方案如下：

1. 将 ​ 合并，得到新堆数目为​，耗费体力为​。

2. 将新堆与第三堆合并，又得到新堆，数目为​，耗费的体力为​。

3. 总共消耗体力为 ​，可以证明​为最小的体力耗费值。

输入格式

输入包括两行，第一行是一个整数 ​，表示果子的种类数。第二行包含 ​ 个整数，用空格分隔，第 ​ 个整数 ​是第 ​ 种果子的数目。

输出

输出包括一行，这一行只包含一个整数，即最小的体力耗费值。

	测试输入	期待的输出	时间限制	内存限制	额外进程
测试用例 1	以文本方式显示 3↵ 1 2 9↵	以文本方式显示 15↵	1秒	1024KB	0

2 代码

//小根堆是一种特殊形式的完全二叉树,可以使用数组来存储
//注意其中很巧妙的下标2倍关系
//从1开始存,0号元素不使用,可以很好的利用上下标的2倍关系
#include<stdio.h>
#include<stdlib.h>long int* heap;
long int heapSize = 0;  //堆元素个数
long int sum = 0;void swap(long int* a, long int* b) {long int temp;temp = *a;*a = *b;*b = temp;
}//存入新数,从末尾存,然后排序
void put(long int num) {long now, next;heap[++heapSize] = num;  //初始值是0,使用前自增now = heapSize;while (now > 1) {next = now >> 1;  //位运算,相当于/2,速度更快if (heap[now] >= heap[next])   //符合结构,直接退出,其他地方都是有序的break;swap(&heap[now], &heap[next]);  //没有直接退出,说明需要交换now = next;}
}//弹出表头,只能从头操作,然后把最后一个数放到根的位置上,排序处理
long int pop() {long int now = 1, next, res = heap[1];heap[1] = heap[heapSize];heapSize--;while (now * 2 <= heapSize) {  //保证有左分支next = now * 2;if (next < heapSize && heap[next + 1] < heap[next])  //有右分支,而且右分支比左分支小next++;if (heap[now] <= heap[next])break;  //符合结构,直接退出swap(&heap[now], &heap[next]);  //没有直接退出,说明不符合结构,需要交换now = next;   //传递继续操作}return res; //弹出的数
}int main(int argc, char* argv[]) {//freopen("file in.txt","r",stdin);long int n;long int i;long int temp;scanf("%ld", &n);//根据输入的n的大小来申请空间heap = (long int*)malloc(sizeof(long int) * (n + 1));for (i = 1;i <= n;i++) {scanf("%ld", &heap[i]);put(heap[i]);}//只有一堆果子的情况if (n == 1) {printf("0\n");return 0;}while (n > 1) {temp = pop() + pop();  //这两个pop()可不一样哦sum += temp;put(temp);   //存进去,会自动处理成小根堆n--;}printf("%ld\n", sum);return 0;
}