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

相关文章

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

usaco 1.3 Barn Repair(贪心)

思路:用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的M-1个作为间隙,其余地方用木板盖住。 做法: 1.若,板(M) 的数目大于或等于 牛棚中有牛的数目(C),则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则,先对 牛牛们的门牌号排序,然后 用一个数组 blank[ ] 记录两门牌号之间的距离,然后 用数组 an

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*

键盘快捷键:提高工作效率与电脑操作的利器

键盘快捷键:提高工作效率与电脑操作的利器 在数字化时代,键盘快捷键成为了提高工作效率和优化电脑操作的重要工具。无论是日常办公、图像编辑、编程开发,还是游戏娱乐,掌握键盘快捷键都能带来极大的便利。本文将详细介绍键盘快捷键的概念、重要性、以及在不同应用场景中的具体应用。 什么是键盘快捷键? 键盘快捷键,也称为热键或快捷键,是指通过按下键盘上的一组键来完成特定命令或操作的方式。这些快捷键通常涉及同

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 (最大值之和)给定整数序列 a0,⋯,an−1,求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr(其中0≤l≤r<n0≤l≤r<n)表示,对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同,当且仅当下标不同。 例如,当原序列为 [1,2,1,2] 时,要计算子序列 [

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

如何提高 GitHub 的下载速度

如何提高 GitHub 的下载速度 文章目录 如何提高 GitHub 的下载速度1. 注册账号2. 准备好链接3. 创建仓库4. 在码云上下载代码5. 仓库更新了怎么办 一般来说,国内的朋友从 GitHub 上面下载代码,速度最大是 20KB/s,这种龟速,谁能忍受呢? 本文介绍一种方法——利用“码云”,可以大大提高下载速度,亲测有效。 1. 注册账号 去“码云”注册一

C - Word Ladder题解

C - Word Ladder 题解 解题思路: 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数(也就是需要变换多少次) 开始替换时: tips: 字符串下标以0开始 我们定义两个变量a和b,用于记录当前遍历到的字符 首先是判断:如果这时a已经==b了,那么就跳过,不用管; 如果a大于b的话:那么我们就让s中的第i项替换成b,接着就直接输出S就行了。 这样