尧图网络 高端网站定制 · 原创设计
免费咨询热线
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/9/28 15:24:25
Wu.CommTool:工业通信协议调试工具的模块化架构设计与技术实现

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

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

📅 2026/9/8 6:36:46
大模型产品化的三个陷阱:独立开发者的 AI 落地复盘与避坑指南

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

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

📅 2026/9/10 21:56:25
MORE NEWS

更多资讯

📰

嘉立创EDA专业版原理图绘制实战:从网络标签到模块化设计

前阵子有个新人问我:嘉立创EDA专业版画原理图,为什么我画出来总是乱得像毛线团,明明连线都接对了,可一到PCB设计阶段就四处漏风。这个问题我太有感触了。PCB设计的起点不是布线,而是原理图。一张清晰的原理图不仅是电气…

📰

卡丁车语音控制实战:硅麦选型、I²S配置与指令优化

1. 为什么卡丁快跑组的语音控制总“听不懂”——从麦克风选型开始就踩了第一个坑全国大学生智能车竞赛里,“卡丁快跑组”这几年越来越火,规则明确允许语音指令作为辅助控制手段,但真正跑通、稳定、上赛道不翻车的队伍不到三成。我连续带了四届…

📰

Java毕设实战:宠物商务智慧管理系统全解析

毕设季一到,"宠物商务智慧管理系统"这类题目几乎成了Java方向选题的常客。听起来既有电商的商务属性,又带着"智慧"俩字的光环,还能光明正大地上传一份源码——但真上手做的时候,很多人连需求都没理清就开始写…

📰

TCP/UDP网络调试助手源码解析:C++与C#双语言实现与调试避坑

简介:这是一份TCP与UDP网络调试助手的完整资源包,内含可运行的SocketTool工具及C/C#源码实现,适合网络编程初学者与开发者调试TCP、UDP通信场景。压缩包共62个文件、18.71MB,以Qt动态库(dll)、C源码&#x…

📰

Blender建模模式+动态网格编辑+Geometry Script联动工作流详解

做三维内容这些年,我从 Edit Mode 一路用到 Geometry Nodes,见过太多人在“看得见的网格”和“算出来的网格”之间反复横跳。最近几版 Blender 把 Modeling Tools、Mesh Editing 和节点的边界敲掉了一大块:几何节点编辑器的 Modeling Mode 让…

📰

游戏引擎架构的本质:团队分工如何决定底层架构

1. 这不是教科书,是十年引擎团队踩出来的路“游戏引擎架构 001:从团队分工到底层架构”——这个标题里藏着一个被太多教程忽略的真相:引擎不是写出来的,而是长出来的。它不是某个人在深夜敲出的一堆C类,而是一群人、在…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

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

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

📞 💬