当前位置: 首页 > news >正文

【洛谷贪心算法】P1090合并果子

在这里插入图片描述

为了使消耗的体力最小,每次都应该选择当前重量最小的两堆果子进行合并。可以使用优先队列(小根堆)来实现这个过程,优先队列可以自动维护元素的顺序,每次取出堆顶的两个元素(即最小的两个元素)进行合并,然后将合并后的结果重新插入堆中,重复这个过程直到堆中只剩下一个元素。

【算法思路】

  1. 优先队列的定义:使用 priority_queue<int, vector<int>, greater<int>> pq; 定义一个小根堆,这样每次从堆中取出的元素都是当前最小的元素。
  2. 读入数据:通过循环读入每堆果子的重量,并将其加入优先队列。
  3. 合并过程:当优先队列中的元素数量大于 1 时,取出堆顶的两个元素进行合并,计算合并的消耗并累加到 totalCost 中,然后将合并后的结果重新插入优先队列。
  4. 输出结果:当优先队列中只剩下一个元素时,合并过程结束,输出 totalCost,即最小的体力消耗值。

【代码示例】

#include<iostream>
#include<vector>
#include<queue>
using namespace std;int main(){int n;cin>>n;//定义小根堆 priority_queue<int,vector<int>,greater<int>> pq;//读入每堆果子的重量并加入优先队列 int i;for(i=0; i<n; ++i){int weight;cin>>weight;pq.push(weight);}int totalCost = 0;//当堆中元素数量大于1时,继续合并while(pq.size() > 1){//取出最小的两堆果子int a = pq.top();//获取不移除pq.pop();//移除int b = pq.top();pq.pop();//计算合并这两堆果子的消耗int cost = a+b; totalCost += cost;//将合并后的果子堆加入优先队列 pq.push(cost);} //输出最小的体力消耗值 cout<<totalCost<<endl;return 0;
}

相关文章:

【洛谷贪心算法】P1090合并果子

为了使消耗的体力最小&#xff0c;每次都应该选择当前重量最小的两堆果子进行合并。可以使用优先队列&#xff08;小根堆&#xff09;来实现这个过程&#xff0c;优先队列可以自动维护元素的顺序&#xff0c;每次取出堆顶的两个元素&#xff08;即最小的两个元素&#xff09;进…...

【告别双日期面板!一招实现el-date-picker智能联动日期选择】

告别双日期面板&#xff01;一招实现el-date-picker智能联动日期选择 1.需求背景2.DateTimePicker 现状图3.日期选择器实现代码4.日期选择器实现效果图5.日期时间选择器实现代码6.日期时间选择器实现效果图 1.需求背景 在用户使用时间查询时&#xff0c;我们经常需要按月份筛选…...

现今大语言模型性能(准确率)比较

现今大语言模型性能(准确率)比较 表头信息:表的标题为“大语言模型性能比较结果”(英文:Table 1: Large Language Model Performance Comparison Results),表明该表是用于对比不同大语言模型的性能。列信息: 模型:列出参与比较的不同大语言模型名称,包括LLAMA3(70B)…...

程序诗篇里的灵动笔触:指针绘就数据的梦幻蓝图(水文,勿三)

大家好啊&#xff0c;我是小象٩(๑ω๑)۶ 我的博客&#xff1a;Xiao Xiangζั͡ޓއއ 很高兴见到大家&#xff0c;希望能够和大家一起交流学习&#xff0c;共同进步。 这一节我们来学习指针的相关知识&#xff0c;学习内存和地址&#xff0c;指针变量和地址&#xff0c;包…...

在 UniApp 中实现中间凸起 TabBar 的完整指南

如何在 UniApp 中设置中间 TabBar 凸起效果 在移动应用开发中&#xff0c;TabBar 是常见的导航组件&#xff0c;而中间凸起的 TabBar 按钮则是一种流行的设计风格&#xff0c;常用于突出重要功能&#xff08;如发布、拍照等&#xff09;。UniApp 提供了 midButton 属性&#x…...

Redis大key

Redis大key基本概念&#xff0c;影响 Redis 大 key 指在 Redis 中存储了大量数据的键&#xff0c;它会对 Redis 的性能和内存管理产生影响。 大key的定义与value的大小和元素数量有关&#xff0c;但这个定义并不是绝对的&#xff0c;而是相对的&#xff0c;具体取决于系统的使用…...

WPF高级 | WPF 与数据库交互:连接、查询与数据更新

WPF高级 | WPF 与数据库交互&#xff1a;连接、查询与数据更新 前言一、数据库交互基础概念1.1 数据库简介1.2 数据访问技术 二、WPF 与数据库连接2.1 连接字符串2.2 建立连接 三、WPF 中的数据查询3.1 使用ADO.NET进行数据查询3.2 使用 Entity Framework 进行数据查询3.3 使用…...

CogBlobTool工具

CogBlobTool是一款专用于图像斑点检测于分析的 工具&#xff0c;通过灰度值阈值分割和特征过滤&#xff0c;帮助在复杂背景中提取目标区域&#xff0c;并计算几何属性。 效果图 注意&#xff1a;在这里只有一张图像可以不使用模板匹配工具 CogBlobTool工具的功能 斑点检测于…...

C# WinForm程序中如何调试dll接口

公司的SF系统是自主开发的。不同的机种会有不同数据记录保存的需求&#xff0c;尤其是客户SQE更是各种奇思妙想......于是做了一个接口&#xff0c;实践之下效果还不错呢。 每每总是忘记怎么调试接口&#xff0c;特记录下备查。首先要将&#xff0c; 1 DLL项目与WinForms项目…...

自然语言处理:词频-逆文档频率

介绍 大家好&#xff0c;博主又来给大家分享知识了。本来博主计划完成稠密向量表示的内容分享后&#xff0c;就开启自然语言处理中文本表示的讲解。可在整理分享资料的时候&#xff0c;博主发现还有个知识点&#xff0c;必须得单独拎出来好好说道说道。 这就是TF-IDF&#xf…...

【银河麒麟高级服务器操作系统】服务器测试业务耗时问题分析及处理全流程分享

更多银河麒麟操作系统产品及技术讨论&#xff0c;欢迎加入银河麒麟操作系统官方论坛 https://forum.kylinos.cn 了解更多银河麒麟操作系统全新产品&#xff0c;请点击访问 麒麟软件产品专区&#xff1a;https://product.kylinos.cn 开发者专区&#xff1a;https://developer…...

基于大数据的民宿旅馆消费数据分析系统

【大数据】基于大数据的民宿旅馆消费数据分析系统&#xff08;完整系统源码开发笔记详细部署教程&#xff09;✅ 目录 一、项目简介二、项目界面展示三、项目视频展示 一、项目简介 该系统可以揭示民宿市场的消费模式和价格分布情况&#xff0c;帮助理解消费者偏好、价格走势及…...

Spring-AI搭建企业专属知识库 一

环境介绍&#xff1a;Spring3.3.2 JDK 21 POM文件 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation&…...

极简本地体验deepseek大模型教程

一 题外随感&#xff1a;时代之问 就像狄更斯在双城记中所述&#xff0c;“这是最好的时代&#xff0c;这是最坏的时代”。每一代人都有其所处的时代&#xff0c;每一个时代都有其所谓好的一面和不那么好的一面。很多时候随口的一句大环境不好&#xff0c;就似乎给了自己一个最…...

RabbitMQ系列(五)基本概念之Queue

在 RabbitMQ 中&#xff0c;Queue&#xff08;队列&#xff09; 是存储消息的容器&#xff0c;也是消息传递的核心载体。以下是其核心特性与作用的全方位解析&#xff1a; 一、Queue 的定义与核心作用 消息存储容器 Queue 是 RabbitMQ 中实际存储消息的实体&#xff0c;生产者…...

【记录】成为创作者的第 730 天(两年)

收获 还是总在感叹走到今天收获的一切&#xff0c;都是自己曾经不敢想的。 无论是靠自己努力拿到的 Offer&#xff0c;还是在 CSDN 网站上结交的网友和前辈们&#xff0c;都是我莫大的荣幸和财富&#xff0c;感恩一切、感恩自己。 过去一年的收获真的数不胜数&#xff0c;抛…...

深度剖析数据分析职业成长阶梯

一、数据分析岗位剖析 目前&#xff0c;数据分析领域主要有以下几类岗位&#xff1a;业务数据分析师、商业数据分析师、数据运营、数据产品经理、数据工程师、数据科学家等&#xff0c;按照工作侧重点不同&#xff0c;本文将上述岗位分为偏业务和偏技术两大类&#xff0c;并对…...

【XSS】DVWA靶场XSS攻击

一、XSS攻击 1.1. XSS 攻击简介 XSS&#xff08;Cross-Site Scripting&#xff0c;跨站脚本攻击&#xff09;是一种常见的Web安全漏洞&#xff0c;它允许攻击者在受害者的浏览器中执行恶意脚本。攻击者通常通过在Web应用程序中注入恶意脚本代码&#xff08;如JavaScript&…...

Fiddler在Windows下抓包Https

文章目录 1.Fiddler Classic 配置2.配置浏览器代理自动代理手动配置浏览器代理 3.抓取移动端 HTTPS 流量&#xff08;可选&#xff09;解决抓取 HTTPS 失败问题1.Fiddler证书过期了 默认情况下&#xff0c;Fiddler 无法直接解密 HTTPS 流量。需要开启 HTTPS 解密&#xff1a; 1…...

04 路由表的IP分组传输过程

目录 1、路由表的核心结构 2、IP分组传输过程和数据包转发过程 2.1、IP分组传输过程 2.2、数据包转发过程 2.3、IP分组传输过程和数据包转发的区别 3、数据包的变化 3.1、拓扑结构 3.2、传输过程详解&#xff08;主机A → 主机B&#xff09; 3.2.1、主机A发送数据 3.2…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...

Qt 事件处理中 return 的深入解析

Qt 事件处理中 return 的深入解析 在 Qt 事件处理中&#xff0c;return 语句的使用是另一个关键概念&#xff0c;它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别&#xff1a;不同层级的事件处理 方…...