当前位置: 首页 > 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…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...