【ACM】洛谷P1090-合并果子

2024-03-12 09:08
文章标签 合并 洛谷 acm 果子 p1090

本文主要是介绍【ACM】洛谷P1090-合并果子,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

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

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

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

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


输入输出格式

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

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

输出格式:
一个整数,也就是最小的体力耗费值。输入数据保证这个值小于 2^{31} 。

输入输出样例

输入样例#1:

3 
1 2 9 

输出样例#1:

15

说明

对于30%的数据,保证有n \le 1000n≤1000:

对于50%的数据,保证有n \le 5000n≤5000;

对于全部的数据,保证有n \le 10000n≤10000。


题解

思路很简单,每次合并两堆最小的,然后再排序再合并。
就是一个 哈夫曼树

使用优先队列解决:

代码
#include<bits/stdc++.h>using namespace std;// 优先队列从小到大排列
priority_queue<int, vector<int>, greater<int> > q;int main() {/** 使用优先队列*/int n,x,a,b,ans=0;cin>>n;for (int i = 0; i < n; ++i) {scanf("%d",&x);q.push(x);}while (q.size()>1) {a=q.top();q.pop();b=q.top();q.pop();q.push(a+b);ans+=(a+b);}cout<<ans;return 0;
}

这篇关于【ACM】洛谷P1090-合并果子的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

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

day-51 合并零之间的节点

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

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

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

【Python从入门到进阶】64、Pandas如何实现数据的Concat合并

接上篇《63.Pandas如何实现数据的Merge》 上一篇我们学习了Pandas如何实现数据的Merge,本篇我们来继续学习Pandas如何实现数据的Concat合并。 一、引言 在数据处理过程中,经常需要将多个数据集合并为一个统一的数据集,以便进行进一步的分析或建模。这种需求在多种场景下都非常常见,比如合并不同来源的数据集以获取更全面的信息、将时间序列数据按时间顺序拼接起来以观察长期趋势等

线性表中顺序表的合并

对两个顺序表进行合并,算法的复杂度为O(La.size+Lb.size)。 已知: 顺序线性表La和Lb的元素按值非递减排列 归并La和Lb得到的顺序线性表Lc,Lc的元素也按值非递减排列。 代码定义: void mergeList(SeqList *La,SeqList *Lb,SeqList *Lc){Lc->capacity = La->size + Lb->size;Lc->b

为libpng不同架构创建构建目录、编译、安装以及合并库文件的所有步骤。

好的。既然你已经有了 libpng 的源代码,并且当前处在它的目录下,我们可以简化脚本,不再需要下载和解压源代码这一步。以下是修改后的脚本:```sh#!/bin/bash# 当前目录即 libpng 源代码目录LIBPNG_SRC_DIR=$(pwd)# 设置工作目录WORK_DIR=$(pwd)/libpng_buildBUILD_DIR_X86_64="$WORK_DIR/build

listview与复选框的合并使用

在使用listview的过程中,我们常常需要使用复选框,实现一些批处理功能。这时候我们需使用自定义的adapter,实现相关复选框的事件响应。      首先在adapter定义一个哈希表,用于存放复选框的选中情况:      如private static HashMap<String,Boolean> isSelected,private static HashMap<Inter

高精度计算(代码加解析,洛谷p1601,p1303)除法待更新

目录 高精度加法 高精度减法 高精度乘法 高精度加法 我们知道在c++语言中任何数据类型都有一定的表示范围。当两个被加数很大时,正常加法不能得到精确解。在小学,我们做加法都采用竖式方法。那么我们也只需要按照加法进位的方式就能得到最终解。 8 5 6+ 2 5 5-------1 1 1 1 加法进位: c[i] = a[i] + b[i];if(c[i] >=

【转载】ACM感悟

今天看了一篇我们学校前辈的ACM的感悟,觉得写的十分有道理,这里转载,文章还会不断的改进和更新。 原文链接:http://www.cnblogs.com/Chierush/p/3760870.html?ADUIN=1339764596&ADSESSION=1401536826&ADTAG=CLIENT.QQ.5329_.0&ADPUBNO=26349 声明:本文是写给弱校ACM新手的一点