[NOIP2004 提高组]合并果子(贪心,优先队列,小根堆一口气学会)

本文主要是介绍[NOIP2004 提高组]合并果子(贪心,优先队列,小根堆一口气学会),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在这里插入图片描述
题目链接洛谷P1090

题意

意思就是给你一堆数(比如1 2 3)
让你加到只剩一个数(1+2+3=6)
每次加的代价是加出来的数(1+2=3 , 代价是3 ; 3+3=6 , 代价是6 ; 6+3为总代价)
要求最小代价(引入一种思想:贪心)

贪心

贪心算法,其实根本不用讲,它的核心思路就是求出局部最优解,走一步算一步,每一步都选当前的最优解,根本不从整体上考虑,然后把所有局部解求出来合成整体解。
举个例子,小红邀请小明和小军到小红家玩,但是小红家比较小,只能容纳两人在这里插入图片描述
从图上可以看出,小军无论怎么走都要走2km,然而小明有两条路可以走,一条是1km,一条是3km,如果你是小明,你会怎么走呢,很明显,走1km这条路,就可以愉快地跟小红一起玩耍了。
这就是贪心,选择局部的最优解,然后凑成整体的最优解,如果还不能理解
在这里插入图片描述
那么这次你会作何选择呢,当然是一直往前,而不是弯着走,但是你思考的时候,其实有把它们分开看,也就是,小明和小红家之间有一个必经中转点,所以要到达小红家就得先到必经中转点,到达必经中转点的最优路径是1,而必经中转点到小红家的最优路径也是1,所以这么走最快
你会发现,最终的答案是由局部得来的,而且依赖于前面的选择(不理解可以想想在小明到必经中转点那条2km的路径上再加一个点,然后把这个新点到达必经中转点的路径删掉,这样就到不了小红家了,所以它依赖于前面的选择),这就是贪心

回归题目

讲了这么多,贪心应该懂了吧,现在回归题目,怎么求最小代价呢,那就分成局部问题吧,局部问题就是合成两堆果子的最小代价对吧,而合成两堆果子的最小代价很显然求,就是把这一大堆果子里把最小的两堆果子合在一起吧?
那解法就昭然若揭了,我们把这堆果子放进一个数据结构里,然后对它从小到大排序,每次取出最小的两个出来,加起来,放到最后,然后再排序一次,让这个新合成的果子找到自己的位置,循环往复,直到只有一堆,合成的过程记录一下代价就好了。

但是每次都排序这样的时间复杂度很大,即使是STL里的sort,每次排序也要 O(nlogn) 的时间,那么有什么数据结构能很快地完成排序这个重要的任务呢

堆是一种特殊的二叉树,它分为小根堆,大根堆
树之所以叫树呢,是因为它长这样
在这里插入图片描述
你也可以这么看它
在这里插入图片描述
第一个"爸爸"结点呢,就叫根结点,每个结点有几个儿子就叫几叉树,但是按照爸爸的数值比儿子小这种存储方式的树,叫小根堆爸爸存的数值比儿子大这种存储方式的树,叫做大根堆
也就是说,在大根堆里,最大的数,是根节点,在小根堆里,最小的数是根节点
我们一般用数组来模拟树,比如 tree[100] tree[1]为根结点,tree[2]和tree[3]为1的子结点,也就是,一个结点的儿子在数组中的位置为i*2i*2+1这样就不会有重复,而且能很快查询父亲或者儿子了

用小根堆的代码如下,注解很多,如果不要注解,可以往下翻

有注解版

#include<bits/stdc++.h>
#define op <		//将此处的<号改成>号即为大根堆 
using namespace std; 
int heap[1000086]/*堆*/, size/*堆的长度*/;
void swim(int n)
{//接下来这段要熟悉for循环的执行顺序//for ( 循环开始时执行且只执行一次 ; 1  ; 3 ) {  2  } for (int i=n ; i>1/*不是根节点就上浮*/&&heap[i] op heap[i / 2]/*跟父结点比较*/ ; i /= 2)swap(heap[i], heap[i / 2]);
}//将子节点与父节点进行比较,不断上浮 
int son(int n)//如果左儿子比右儿子小,返回左儿子,不然返回右儿子 
{//此处的处理有点巧妙,本来是要比较左儿子与右儿子的大小//但是因为n的左儿子是2*n,右儿子是2*n+1//所以用一个判断式来代表这个1存不存在//下面的2*n是左右儿子的公有部分 //如果你觉得这样很复杂,可以重新写一个思路一样的更简单的,但是更长的代码 return n

这篇关于[NOIP2004 提高组]合并果子(贪心,优先队列,小根堆一口气学会)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/498379

相关文章

使用Apache POI在Java中实现Excel单元格的合并

《使用ApachePOI在Java中实现Excel单元格的合并》在日常工作中,Excel是一个不可或缺的工具,尤其是在处理大量数据时,本文将介绍如何使用ApachePOI库在Java中实现Excel... 目录工具类介绍工具类代码调用示例依赖配置总结在日常工作中,Excel 是一个不可或缺的工http://

Spring Boot整合消息队列RabbitMQ的实现示例

《SpringBoot整合消息队列RabbitMQ的实现示例》本文主要介绍了SpringBoot整合消息队列RabbitMQ的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录RabbitMQ 简介与安装1. RabbitMQ 简介2. RabbitMQ 安装Spring

使用Python创建一个能够筛选文件的PDF合并工具

《使用Python创建一个能够筛选文件的PDF合并工具》这篇文章主要为大家详细介绍了如何使用Python创建一个能够筛选文件的PDF合并工具,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录背景主要功能全部代码代码解析1. 初始化 wx.Frame 窗口2. 创建工具栏3. 创建布局和界面控件4

Python自动化办公之合并多个Excel

《Python自动化办公之合并多个Excel》在日常的办公自动化工作中,尤其是处理大量数据时,合并多个Excel表格是一个常见且繁琐的任务,下面小编就来为大家介绍一下如何使用Python轻松实现合... 目录为什么选择 python 自动化目标使用 Python 合并多个 Excel 文件安装所需库示例代码

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque

解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)

《解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)》该文章介绍了使用Redis的阻塞队列和Stream流的消息队列来优化秒杀系统的方案,通过将秒杀流程拆分为两条流水线,使用Redi... 目录Redis秒杀优化方案(阻塞队列+Stream流的消息队列)什么是消息队列?消费者组的工作方式每

使用Python合并 Excel单元格指定行列或单元格范围

《使用Python合并Excel单元格指定行列或单元格范围》合并Excel单元格是Excel数据处理和表格设计中的一项常用操作,本文将介绍如何通过Python合并Excel中的指定行列或单... 目录python Excel库安装Python合并Excel 中的指定行Python合并Excel 中的指定列P

Redis延迟队列的实现示例

《Redis延迟队列的实现示例》Redis延迟队列是一种使用Redis实现的消息队列,本文主要介绍了Redis延迟队列的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录一、什么是 Redis 延迟队列二、实现原理三、Java 代码示例四、注意事项五、使用 Redi

基于C#实现PDF文件合并工具

《基于C#实现PDF文件合并工具》这篇文章主要为大家详细介绍了如何基于C#实现一个简单的PDF文件合并工具,文中的示例代码简洁易懂,有需要的小伙伴可以跟随小编一起学习一下... 界面主要用于发票PDF文件的合并。经常出差要报销的很有用。代码using System;using System.Col

Python视频剪辑合并操作的实现示例

《Python视频剪辑合并操作的实现示例》很多人在创作视频时都需要进行剪辑,本文主要介绍了Python视频剪辑合并操作的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录介绍安装FFmpegWindowsMACOS安装MoviePy剪切视频合并视频转换视频结论介绍