P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G题解

2024-02-17 00:28

本文主要是介绍P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过n−1次合并之后, 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家,所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1,并且已知果子的种类 数和每种果子的数目,你的任务是设计出合并的次序方案,使多多耗费的体力最少,并输出这个最小的体力耗费值。

例如有3种果子,数目依次为1 ,2,9 。可以先将1 、2堆合并,新堆数目为3 ,耗费体力为3 。接着,将新堆与原先的第三堆合并,又得到新的堆,数目为12 ,耗费体力为12 。所以多多总共耗费体力=3+12=15 。可以证明15为最小的体力耗费值。

输入输出格式

输入格式

共两行。
第一行是一个整数n(1≤n≤10000) ,表示果子的种类数。

第二行包含n个整数,用空格分隔,第i个整数a_{i}​(1≤a_{i}≤20000) 是第i种果子的数目。

输出格式

一个整数,也就是最小的体力耗费值。输入数据保证这个值小于231 。 

输入输出样例

输入样例

3 
1 2 9 

输出样例

15

解析

这个题目使用的是哈夫曼编码的思想,只需要每次将最小的两个果堆合并成一个果堆即可。实现的方式可以使用优先队列或者二叉堆。这里采用建立两个数组的方式,第一个数组存储每堆果子的重量并从小往大排序。从第一个数组中取出前两个就是最小的两堆果子。把这两堆果子取出(从数组中划掉)合并一次成为新的一堆,记录现在的体力,然后把这两堆果子的总和放在第二个数组后面。接下来继续找最小堆果子,只需要比较两个数组中没有被划掉的部分最前面的元素即可,取出,然后用同样的方法找到最小的另外一堆,合并,也放到第二个数组中。这两个数组都是从小到大排序的,所以这两个数组中最小的一堆一定就在两个数组没有被划掉的元素的最头部。重复这样的操作,直到最后两堆果子被合并。

可以使用两个书签来定位数组的哪些元素之前被划掉了,书签的位置就是没有被划掉的头部,此外还要记录下两个数组中元素的个数。同时将数组初始化为一个很大的数字,否则如果初始化为0,则可能被当作果子被取出。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,n2,a1[10010],a2[10010],sum=0;
int main(){cin>>n;memset(a1,127,sizeof(a1));//将数组初始化为一个接近int最大值的数,效率最高 memset(a2,127,sizeof(a2));for(int i=0;i<n;i++){cin>>a1[i];}sort(a1,a1+n);int i=0,j=0,k,w;for(int k=1;k<n;k++){w=a1[i]<a2[j]?a1[i++]:a2[j++];//取最小值 w+=a1[i]<a2[j]?a1[i++]:a2[j++];//取两次最小值 a2[n2++]=w;//加入第二个队列 sum+=w;//计算体力 }cout<<sum;
}

注意:使用memset初始化int数组时,第二个参数如果是0,数组就会被初始化为0;如果是127,会初始化为一个很大且接近int类型上限的正数;如果是128,会初始化成很小且接近int类型下限的负数;如果是-1或者255时,数组会初始化为-1。

这篇关于P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Python实现合并与拆分多个PDF文档中的指定页

《Python实现合并与拆分多个PDF文档中的指定页》这篇文章主要为大家详细介绍了如何使用Python实现将多个PDF文档中的指定页合并生成新的PDF以及拆分PDF,感兴趣的小伙伴可以参考一下... 安装所需要的库pip install PyPDF2 -i https://pypi.tuna.tsingh

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

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

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

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

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

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

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

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

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

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

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

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

不删数据还能合并磁盘? 让电脑C盘D盘合并并保留数据的技巧

《不删数据还能合并磁盘?让电脑C盘D盘合并并保留数据的技巧》在Windows操作系统中,合并C盘和D盘是一个相对复杂的任务,尤其是当你不希望删除其中的数据时,幸运的是,有几种方法可以实现这一目标且在... 在电脑生产时,制造商常为C盘分配较小的磁盘空间,以确保软件在运行过程中不会出现磁盘空间不足的问题。但在

在C#中合并和解析相对路径方式

《在C#中合并和解析相对路径方式》Path类提供了几个用于操作文件路径的静态方法,其中包括Combine方法和GetFullPath方法,Combine方法将两个路径合并在一起,但不会解析包含相对元素... 目录C#合并和解析相对路径System.IO.Path类幸运的是总结C#合并和解析相对路径对于 C

如何提高Redis服务器的最大打开文件数限制

《如何提高Redis服务器的最大打开文件数限制》文章讨论了如何提高Redis服务器的最大打开文件数限制,以支持高并发服务,本文给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录如何提高Redis服务器的最大打开文件数限制问题诊断解决步骤1. 修改系统级别的限制2. 为Redis进程特别设置限制