13. 郭老师爱合并果子
1 题目描述
郭老师爱合并果子
| 成绩 | 20 | 开启时间 | 2021年10月8日 星期五 18:00 |
| 折扣 | 0.8 | 折扣时间 | 2021年10月26日 星期二 00:00 |
| 允许迟交 | 否 | 关闭时间 | 2021年12月1日 星期三 00:00 |
郭老师家有个果园，每年到了秋收的时候都会收获很多不同种类的果子。他决定把所有的果子合成一堆，但由于体力有限，郭老师在每次合并的时候只能将两堆果子合并到一起。假设有 堆果子，那么经过 次合并即可完成任务，且消耗的总体力等于每次合并所消耗的体力之和。
因为郭老师还需要保留体力将果子运回家，所以在合并果子过程中要尽可能地节省体力。假定每个果子重量均为，并且已知果子的种类数和每种果子的数目，你的任务是设计出合理的合并方案，使郭老师耗费的体力最少。
例如有种果子，数目依次为。合并方案如下：
将 合并，得到新堆数目为，耗费体力为。
将新堆与第三堆合并，又得到新堆，数目为，耗费的体力为。
总共消耗体力为 ，可以证明为最小的体力耗费值。
输入格式
输入包括两行，第一行是一个整数 ，表示果子的种类数。第二行包含 个整数，用空格分隔，第 个整数 是第 种果子的数目。
输出
输出包括一行，这一行只包含一个整数，即最小的体力耗费值。
| 测试输入 | 期待的输出 | 时间限制 | 内存限制 | 额外进程 | |
|---|---|---|---|---|---|
| 测试用例 1 | 以文本方式显示
| 以文本方式显示
| 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;
}