尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
【题解-信息学奥赛一本通】1369:合并果子(fruit)
题目148. 合并果子题目描述在一个果园里达达已经将所有的果子打了下来而且按果子的不同种类分成了不同的堆。达达决定把所有的果子合成一堆。每一次合并达达可以把两堆果子合并到一起消耗的体力等于两堆果子的重量之和。可以看出所有的果子经过 n−1 次合并之后就只剩下一堆了。达达在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家所以达达在合并果子时要尽可能地节省体力。假定每个果子重量都为 1并且已知果子的种类数和每种果子的数目你的任务是设计出合并的次序方案使达达耗费的体力最少并输出这个最小的体力耗费值。例如有 3 种果子数目依次为 129。可以先将 1、2 堆合并新堆数目为 3耗费体力为 3。接着将新堆与原先的第三堆合并又得到新的堆数目为 12耗费体力为 12。所以达达总共耗费体力31215。可以证明 15 为最小的体力耗费值。输入输入包括两行第一行是一个整数 n表示果子的种类数。第二行包含 n 个整数用空格分隔第 i 个整数 ai是第 i 种果子的数目。输出输出包括一行这一行只包含一个整数也就是最小的体力耗费值。输入数据保证这个值小于 231。数据范围1 ≤ n ≤ 10000,1 ≤ ai≤ 20000时空限制1s / 64MB输入样例3 1 2 9输出样例15思路与算法简单证明每次合并两种最小数目的果子这样消耗体力之和最小。设合并n种果子所消耗的体力之和为F(n)果子种最小数目分别为a和b。F(n)F(n-1)ab。每次都先合并两种最小数目的果子可以看成先合并其他n-1种果子最后加上a和b。所以合并n-1种果子的局部最优解可以推导出n种果子的全局最优解。代码#includeiostream#includequeueusingnamespacestd;intn;intmain(){scanf(%d,n);priority_queueint,vectorint,greaterintheap;while(n--){intx;scanf(%d,x);heap.push(x);}intres0;while(heap.size()1){intaheap.top();heap.pop();intbheap.top();heap.pop();resab;heap.push(ab);}printf(%d,res);return0;}结果
RELATED

相关推荐

ROB101 Computational Linear Algebra:开启机器人学数学基础的终极指南

ROB101 Computational Linear Algebra:开启机器人学数学基础的终极指南

ROB101 Computational Linear Algebra:开启机器人学数学基础的终极指南 【免费下载链接】rob101 Pilot course for Robotics 101: Computational Linear Algebra 项目地址: https://gitcode.com/gh_mirrors/ro/rob101 ROB101 Computational Linear Algebra是…

📅 2026/11/15 19:57:38
Wu.CommTool:工业通信协议调试工具的模块化架构设计与技术实现

Wu.CommTool:工业通信协议调试工具的模块化架构设计与技术实现

Wu.CommTool:工业通信协议调试工具的模块化架构设计与技术实现 【免费下载链接】Wu.CommTool 基于C#、WPF、Prism、MaterialDesign、HandyControl开发的通讯调试工具。支持Modbus Rtu调试、Mqtt调试、TCP调试、串口调试、UDP调试 项目地址: https://gitcode.com/g…

📅 2026/11/15 19:57:38
大模型产品化的三个陷阱:独立开发者的 AI 落地复盘与避坑指南

大模型产品化的三个陷阱:独立开发者的 AI 落地复盘与避坑指南

大模型产品化的三个陷阱:独立开发者的 AI 落地复盘与避坑指南 一、当「接个 API」变成「重构整个产品」 独立开发者接入大模型的第一天,通常充满乐观:注册账号、复制 API Key、写几行代码调用 chat.completions.create(),然后感…

📅 2026/10/13 17:41:06
MORE NEWS

更多资讯

📰

证书过期了不知道怎么复审延期?考电工证考哪个有用良心建议来了

证书过期了不知道怎么复审延期?考电工证考哪个有用良心建议来了 证书过期了不知道怎么复审延期?这事儿不少电工朋友都遇到过,尤其是一些刚入行的朋友,可能对证照管理不太熟悉,一不小心就错过了复审时间,耽误了工作。今天就从 考电工证考哪个有用…

📰

广州电工证怎查询?上岗必备证书怎么查真伪与用途全解析

广州电工证怎查询?上岗必备证书怎么查真伪与用途全解析 急需特种作业证才能上岗找工作,这是很多建筑、电力、制造业从业人员的真实写照。电工证作为特种作业操作证之一,是从事电气作业的“上岗必备”证明,尤其在广州这样的制造业和建筑业重镇,持有电工证…

📰

进网电工证是否取消千万别踩坑,学历不高也能报名的全流程解析

进网电工证是否取消千万别踩坑,学历不高也能报名的全流程解析 你是不是听说进网电工证要取消了,心里打鼓不敢报名?其实这事儿你不用太担心,但得搞清楚真相,别一不小心踩坑。特别是像你这样学历不高,但又有电工手艺的朋友,更要搞懂到底能不能报,怎么报…

📰

禄丰市电工证培训中心怎么报名?外省证能不能转过来?

禄丰市电工证培训中心怎么报名?外省证能不能转过来? 之前考的证在外省能不能转过来?这个问题我听过不下百次。说实话,很多人在外地打工、考试,回来后才发现证书不在本地,或者不符合本地的管理要求,心里急得慌。特别是电工证这种高频使用、监管严格的特…

📰

宿迁低压电工证培训班怎么考?网上查询最全干货来了

宿迁低压电工证培训班怎么考?网上查询最全干货来了 工地太忙根本没时间复习考试,这是很多在宿迁打工的建筑工人心声。特别是低压电工证,不仅是上岗的“通行证”,更是安全作业的“底线”,但很多工友因为工作忙、不懂流程,错过了报名和考试机会,甚至因为…

📰

学生电工证怎么考取在哪考,别被中介坑了

学生电工证怎么考取在哪考,别被中介坑了 你是不是也遇到过这种情况?想考电工证,却不知道 在哪考 ,结果被各种培训机构忽悠,花了不少钱,最后还可能拿不到正规证书?别急,这篇文章就是为了帮你理清楚整个流程,让你少走弯路,顺利拿到证书。…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬