您现在的位置是:首页 > 正文

[AcWing] 148. 合并果子(C++实现)贪心---哈夫曼树例题

2024-01-30 19:42:11阅读 0

1. 题目

在这里插入图片描述
在这里插入图片描述

2. 读题(需要重点注意的东西)

思路:

贪心 -----> 每次在当前的选法中,选择能选的情况中的最优解

解题思路
每次取最小的两堆合并成一堆,然后重复,直至最后只有一堆。


代码实现思路:
用小根堆保存所有的数,每次合并时,pop出两个数求和,然后将这两个数的和push进小根堆即可

3. 解法

---------------------------------------------------解法---------------------------------------------------

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);

    priority_queue<int, vector<int>, greater<int>> heap;
    while (n -- )
    {
        int x;
        scanf("%d", &x);
        heap.push(x);
    }

    int res = 0;
    while (heap.size() != 1)
    {
        int a = heap.top(); heap.pop();
        int b = heap.top(); heap.pop();
        res += a + b;
        heap.push(a + b); // 注意这里是push a+b,不是push res
    }

    printf("%d\n", res);
    return 0;
}

可能存在的问题(所有问题的位置都在上述代码中标注了出来)

4. 可能有帮助的前置习题

5. 所用到的数据结构与算法思想

  • 贪心

6. 总结

贪心思想、哈夫曼树的例题,理解思想并自行推导出代码。

哈夫曼树的核心:每次合并两个最小的堆,直至全部合并完即可。

网站文章

  • 计算机级C语言实例:使用C#编写的简单计算器

    然后,使用Console.ReadLine()函数接收用户输入的两个数字和运算符,并将它们转换为相应的数据类型。如有任何疑问,请随时提问。在本篇文章中,我们将使用C#编写一个简单的计算器应用程序。最后...

    2024-01-30 19:42:06
  • IL伪指令

    IL伪指令 在IL程序中,以“.”开头的指令代表是将要传输给汇编工具的指令,即伪指令。该指令要汇编工具执行某些具体操作。.assembly <程序集名称> {}//指明IL码属于那个程序集。.method 修饰符 返回值 名称(参数列表){...

    2024-01-30 19:41:26
  • 微型计算机usb接口通常串行,第一章-微型计算机组成题库.doc

    《第一章微型计算机组成概述》练习判断题1. 光盘是一种可读不可写的存储器。2. 显示器直接与PCI-E接口相连。3. 激光打印机使用的墨水质量很高。4.SRAM比DRAM速度慢。5.ROM是非易失性存...

    2024-01-30 19:41:19
  • 上海电力学院计算机辅助设计2,上海电力学院电路计算机辅助设计2--二端口电路的设计...

    上海电力学院计算机辅助设计2,上海电力学院电路计算机辅助设计2--二端口电路的设计...

    上海电力学院电路计算机辅助设计2--二端口电路的设计实验一:二端口电路的设计一、电路课程设计目的1、掌握二端口网络的基本概念和形成端口的条件。2、熟练掌握二端口网络的Y参数、Z参数、T参数方程,理解各...

    2024-01-30 19:41:11
  • 通过bat脚本一键安装mysql-5.7.27-win32

    通过bat脚本一键安装mysql-5.7.27-win32

    一、在D:\MySQL路径下,新建一个空文件夹Database,并将mysql-5.7.27-win32文件夹也放在该路径下; 二、在D:\MySQL\mysql-5.7.27-win32路径下,依次新建my.ini,my2.ini,1022.sql,install.bat四个文件; 1.my.ini内容如下: [mysqld] # 设置3306端口 port=3306 # 设置m...

    2024-01-30 19:40:42
  • CMAKE入门

    CMAKE入门

    title: CMAKE入门date: 2021-05-24 19:03:56description:What CMake can do跨平台构建  一套C/C++代码,多平台运行。假设在Window...

    2024-01-30 19:40:36
  • strace神器的使用方法详解与实践

    strace 详解

    2024-01-30 19:40:30
  • 【目标检测系列】sppnet网络介绍

    【目标检测系列】sppnet网络介绍

    上链接 好多文章写,感觉这个是我能读懂的。 https://www.cnblogs.com/gongxijun/p/7172134.html 尤其对那张图的解释,很赞。大部分文章把图一贴,也不解释或者干脆解释不清楚。。。。。。 ...

    2024-01-30 19:40:02
  • javascript将字符串转换成数字

    Number()对参数value进行整体转换,当参数值中任何地方包含了无法转换为数字的符号时,转换失败,此时将返回NaN,否则返回转换后的数字。如果在参数前面包含了除空格、+和-以外的其他特殊符号或非...

    2024-01-30 19:39:55
  • Git分支版本管理

    Git分支版本管理

    Git分支版本管理   现在主流的代码管理工具基本上就是git了,svn虽然说也有人在用,但是毕竟不是那么的多了,git就不一样了,依旧是在呗大多数人所接受着,国内一般人使用的是开源中国的git库管理...

    2024-01-30 19:39:48