广西南宁电商网站建设,wordpress 答题主题,成都建设材料二维码网站,cms内容网站管理系统1 题目描述
郭老师爱合并果子成绩20开启时间2021年10月8日 星期五 18:00折扣0.8折扣时间2021年10月26日 星期二 00:00允许迟交否关闭时间2021年12月1日 星期三 00:00 郭老师家有个果园#xff0c;每年到了秋收的时候都会收获很多不同种类的果子。他决定把所有的果子合成一堆每年到了秋收的时候都会收获很多不同种类的果子。他决定把所有的果子合成一堆但由于体力有限郭老师在每次合并的时候只能将两堆果子合并到一起。假设有 堆果子那么经过 次合并即可完成任务且消耗的总体力等于每次合并所消耗的体力之和。因为郭老师还需要保留体力将果子运回家所以在合并果子过程中要尽可能地节省体力。假定每个果子重量均为并且已知果子的种类数和每种果子的数目你的任务是设计出合理的合并方案使郭老师耗费的体力最少。例如有种果子数目依次为。合并方案如下将 合并得到新堆数目为耗费体力为。将新堆与第三堆合并又得到新堆数目为耗费的体力为。总共消耗体力为 可以证明为最小的体力耗费值。输入格式输入包括两行第一行是一个整数 表示果子的种类数。第二行包含 个整数用空格分隔第 个整数 是第 种果子的数目。输出输出包括一行这一行只包含一个整数即最小的体力耗费值。 测试输入 期待的输出 时间限制 内存限制 额外进程 测试用例 1以文本方式显示3↵1 2 9↵以文本方式显示15↵1秒1024KB0 2 代码
//小根堆是一种特殊形式的完全二叉树,可以使用数组来存储
//注意其中很巧妙的下标2倍关系
//从1开始存,0号元素不使用,可以很好的利用上下标的2倍关系
#includestdio.h
#includestdlib.hlong 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;
}
