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

OJ万题详解––[NOIP2004 提高组] 合并果子(C++详解)

目录

题目

分析

参考代码


题目

题目描述

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

每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过n-1次合并之后,就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家,所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使多多耗费的体力最少,并输出这个最小的体力耗费值。

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

输入格式

输入包括两行。

第一行是一个整数n(1<=n<=10000),表示果子的种类数。

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

输出格式

输出包括一行,这一行只包含一个整数,也就是最小的体力耗费值。输入数据保证这个值小于2的31次方。 

样例

样例输入

3 
1 2 9 

样例输出

15

数据范围与提示

对于30%的数据,保证有n<=1000:

对于50%的数据,保证有n<=5000;

对于全部的数据,保证有n<=10000。

分析

这道题我主要是采用优先队列的方式来做,主要是因为优先队列便于排序.

接下来咱们边上代码边讲

priority_queue<int,vector<int>,greater<int> >q;

定义优先队列,这里我定义的是小根堆(从小到大),因为优先队列默认的是大根堆(从大到小),为了避免与输入流符号">>"误认,要特地把他们分开.

for(int i=1;i<=n;i++){cin>>tmp;q.push(tmp);
}

输入,入列,优先队列的好处就是边入列边排序,比sort快.

while(q.size()>1){k=q.top();q.pop();k1=q.top();q.pop();k1+=k,sum+=k1;q.push(k1);k1=0;
}

合并果子的过程,大家应该都能看懂吧 .

最后把sum输出就行了.接下来就是参考代码

参考代码

#include<bits/stdc++.h>
using namespace std;
const int MAX=10005;
typedef unsigned long long ull;
int tmp,n,sum,k,k1;
priority_queue<int,vector<int>,greater<int> >q;
int main(){ios::sync_with_stdio(false);cin>>n;for(int i=1;i<=n;i++){cin>>tmp;q.push(tmp);}while(q.size()>1){k=q.top();q.pop();k1=q.top();q.pop();k1+=k,sum+=k1;q.push(k1);k1=0;}cout<<sum<<endl;return 0;
}

如果你不想让你的代码超时,手动开O2哦

#pragma GCC optimize(2)

相关文章:

OJ万题详解––[NOIP2004 提高组] 合并果子(C++详解)

目录 题目 分析 参考代码 题目 题目描述 一个果园里&#xff0c;多多已经将所有的果子打了下来&#xff0c;而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并&#xff0c;多多可以把两堆果子合并到一起&#xff0c;消耗的体力等于两堆果子的…...

MySQL-字符集和比较规则

在计算机中只能存储二进制数据&#xff0c;那该怎么存储字符串呢&#xff1f;当然是建立字符与二进制数据的映射关系 了&#xff0c;建立这个关系最起码要搞清楚两件事&#xff1a; 界定清楚字符范围&#xff1a;需要把哪些字符映射成二进制数据&#xff1f;编码与解码&#x…...

微搭低代码从入门到精通12-网格布局

开发小程序首要的就是考虑布局的问题&#xff0c;我们在以前的版本只能选择普通容器结合图片和文本组件来构建页面。 使用通用组件布局也可以&#xff0c;但有个问题是你要先学习CSS&#xff0c;要懂布局的概念&#xff0c;比如需要知道啥是flex布局&#xff0c;然后还得熟悉每…...

【c语言】二叉树

主页&#xff1a;114514的代码大冒险 qq:2188956112&#xff08;欢迎小伙伴呀hi✿(。◕ᴗ◕。)✿ &#xff09; Gitee&#xff1a;庄嘉豪 (zhuang-jiahaoxxx) - Gitee.com 引入 我们之前已经学过线性数据结构&#xff0c;今天我们将介绍非线性数据结构----树 树是一种非线性的…...

六、Java框架之SpringBoot

黑马课程 文章目录1. SpringBoot入门1.1 SpringBoot入门案例步骤1&#xff1a;创建SpringBoot项目高版本springboot常见错误步骤2&#xff1a;创建BookController步骤3&#xff1a;启动服务器并运行程序pom.xml示例1.2 官网创建SpringBoot1.3 SpringBoot工程快速启动问题导入打…...

「Python|环境安装|Windows」如何在Windows上安装Python环境?

本文主要介绍如何在Windows上安装Python&#xff0c;帮助初学者或者非程序员伙伴快速搭建可以运行python代码的环境。 文章目录安装python做一点小配置验证python如何安装指定版本的python编程语言的环境搭建一直是学习编程的第一道门槛。 对于如何在Linux系统上安装指定版本的…...

人工智能轨道交通行业周刊-第33期(2023.2.6-2.12)

本期关键词&#xff1a;高铁激光清洗、高铁确认列车、无线通信系统、推理服务优化、量子信息技术 1 整理涉及公众号名单 1.1 行业类 RT轨道交通中关村轨道交通产业服务平台人民铁道世界轨道交通资讯网铁路信号技术交流北京铁路轨道交通网上榜铁路视点ITS World轨道交通联盟V…...

五分钟看懂Java字节码:极简手册

字节码新手很容易被厚厚的 JVM 书籍劝退&#xff0c;即使我看过相关书籍&#xff0c;工作真正用到时也全忘了&#xff0c;还得现学。 等我有了一定的字节码阅读经验&#xff0c;才发现字节码其实非常简单&#xff0c;只需要三步就能快速学会&#xff1a; 先了解 JVM 的基本结…...

C++ 类与对象(下)

✅<1>主页&#xff1a;我的代码爱吃辣 &#x1f4c3;<2>知识讲解&#xff1a;C &#x1f525;<3>创作者&#xff1a;我的代码爱吃辣 ☂️<4>开发环境&#xff1a;Visual Studio 2022 &#x1f4ac;<5>前言&#xff1a;C类与对象的收尾工作&#…...

Java基础——I/O

一、异常 异常是程序中可能出现的问题&#xff0c;它的父类是Exception。异常分为两类&#xff0c;编译时异常、运行时异常。 编译时异常&#xff1a;没有继承RuntimeException的异常&#xff0c;直接继承于Exception。编译阶段就会错误提示。运行时异常&#xff1a;RuntimeE…...

关于@hide的理解

在上一篇文章《学习HandlerThread》我们提到虽然HandlerThread类里有getThreadHandler()方法得到Handler&#xff0c;但是我们不可能调用到它。因为这个方法用hide注释了 /*** return a shared {link Handler} associated with this thread* hide*/NonNullpublic Handler getT…...

使用python加密主机文件几种方法实现

本文主要介绍了使用python加密主机文件几种方法实现&#xff0c;文中通过示例代码介绍的非常详细&#xff0c;对大家的学习或者工作具有一定的参考学习价值&#xff0c;需要的朋友们下面随着小编来一起学习学习吧数据加密是一种保护数据安全的技术&#xff0c;通过对数据进行编…...

西湖论剑 2023 比赛复现

WEB real_ez_node 在 route/index.js 中&#xff1a; router.post(/copy,(req,res)>{res.setHeader(Content-type,text/html;charsetutf-8)var ip req.connection.remoteAddress;console.log(ip);var obj {msg: ,}if (!ip.includes(127.0.0.1)) {obj.msg"only for…...

微信小程序更换管理员/重置管理员

方式1&#xff1a; 首先进入微信公众平台官网进入并登录后在管理中找到成员管理选项找到管理员点击后方的修改选项需要使用原管理员的微信进行扫码验证扫码后在手机上确认绑定新管理员&#xff0c;注意&#xff1a;如果是个人账号不可以更改成其他人。 方式2&#xff1a;原管…...

企业进存销管理系统

技术&#xff1a;Java、JSP等摘要&#xff1a;随着当今世界计算机技术的飞速发展&#xff0c;计算机在企业管理中应用的普及&#xff0c;利用计算机实现企业进销存管理势在必行。本系统结合公司实际的进销存制度&#xff0c;通过对本公司的供应商、客户、商品、进货、销售、进销…...

C++入门

变量变量创建的语法: 数据类型 变量名 变量初始值;int a 10;cout << a << endl;常量作用:用于记录程序中不可更改的教国C定义常量两种方式1).#define 宏常量:#define 常量名 常量值通常在文件上方定义。表示一个常量2).const 修饰的变量const 数据类型 常量名 常…...

视频知识点(20)- H264码流如何在SPS中获取宽高信息?

《音视频开发》系列-总览 前沿 了解H264视频编码格式的小伙伴都知道,H264编码中存在两个非常重要的参数集。没错,它们就是序列参数集(SPS)和图像参数集(PPS),而且通常情况下,PPS会依赖SPS中的部分参数信息,同时,视频码流的宽高信息也存储在SPS中。那么如何从中获取视…...

鲜花数据集实验结果总结

从read_split_data中得到&#xff1a;训练数据集&#xff0c;验证数据集&#xff0c;训练标签&#xff0c;验证标签。的所有的具体详细路径 数据集位置&#xff1a;https://download.csdn.net/download/guoguozgw/87437634 import os #一种轻量级的数据交换格式&#xff0c; …...

ElasticJob-Lite架构篇 - 认知分布式任务调度ElasticJob-Lite

前言 本文基于 ElasticJob-Lite 3.x 版本展开分析。 如果 Quartz 集群中有多个服务端节点&#xff0c;任务决定在哪个服务端节点上执行的呢&#xff1f; Quartz 采用随机负载&#xff0c;通过 DB 抢占下一个即将触发的 Trigger 绑定的任务的执行权限。 在 Quartz 的基础上&…...

【直击招聘C++】2.6 对象之间的复制

2.6 对象之间的复制一、要点归纳1. 对象之间的复制操作1.1 运算符1.2 拷贝构造函数2. 对象之间的浅复制和深复制2.1 对象的浅复制2.2 对象的深复制二、面试真题解析面试题1面试题2一、要点归纳 1. 对象之间的复制操作 同一个类的对象之间可以进行复制操作&#xff0c;即将一个…...

Loguru性能优化秘籍:10个技巧让你的日志系统快如闪电

Loguru性能优化秘籍&#xff1a;10个技巧让你的日志系统快如闪电 【免费下载链接】loguru A lightweight C logging library 项目地址: https://gitcode.com/gh_mirrors/log/loguru Loguru是一个轻量级、高性能的C日志库&#xff0c;专为追求极致性能的开发者设计。在当…...

本地视频怎么去水印?2026实测去水印方法汇总,本地视频去水印软件推荐

本地视频怎么去水印&#xff1f;2026实测去水印方法汇总&#xff0c;本地视频去水印软件推荐 视频里的水印是很多人在整理或剪辑素材时遇到的高频问题。有时是平台在视频上自动打上的 Logo&#xff0c;有时是录屏工具留下的品牌标识&#xff0c;还有时是拍摄 App 在画面角落打的…...

基于MCP协议的金融数据服务器:为AI量化分析提供标准化数据接口

1. 项目概述&#xff1a;一个为金融量化分析而生的MCP服务器如果你和我一样&#xff0c;在金融数据分析和量化策略开发的路上摸爬滚打过几年&#xff0c;那你一定对“数据获取”这个老大难问题深有体会。无论是想回测一个简单的双均线策略&#xff0c;还是构建一个复杂的多因子…...

Cursor Pro激活终极指南:深度解析多平台无限制使用方案

Cursor Pro激活终极指南&#xff1a;深度解析多平台无限制使用方案 【免费下载链接】cursor-free-vip [Support 0.45]&#xff08;Multi Language 多语言&#xff09;自动注册 Cursor Ai &#xff0c;自动重置机器ID &#xff0c; 免费升级使用Pro 功能: Youve reached your tr…...

DeepSeek-Coder-V2:架构级革命性突破,重塑企业级代码智能新范式

DeepSeek-Coder-V2&#xff1a;架构级革命性突破&#xff0c;重塑企业级代码智能新范式 【免费下载链接】DeepSeek-Coder-V2 DeepSeek-Coder-V2: Breaking the Barrier of Closed-Source Models in Code Intelligence 项目地址: https://gitcode.com/GitHub_Trending/de/Deep…...

3步轻松搞定:BiliBili-UWP第三方客户端完整使用指南

3步轻松搞定&#xff1a;BiliBili-UWP第三方客户端完整使用指南 【免费下载链接】BiliBili-UWP BiliBili的UWP客户端&#xff0c;当然&#xff0c;是第三方的了 项目地址: https://gitcode.com/gh_mirrors/bi/BiliBili-UWP 还在用浏览器看B站吗&#xff1f;卡顿、高内存…...

NoFences终极指南:免费开源桌面分区工具彻底解决Windows桌面混乱问题

NoFences终极指南&#xff1a;免费开源桌面分区工具彻底解决Windows桌面混乱问题 【免费下载链接】NoFences &#x1f6a7; Open Source Stardock Fences alternative 项目地址: https://gitcode.com/gh_mirrors/no/NoFences 还在为杂乱的Windows桌面而烦恼吗&#xff1…...

VSCode + GitLab 真香组合:告别命令行恐惧,可视化搞定团队代码提交与合并

VSCode GitLab 可视化协作指南&#xff1a;零命令行完成高效团队开发 对于视觉型开发者而言&#xff0c;命令行操作常常是学习Git工作流的最大障碍。当团队采用GitLab进行协作时&#xff0c;传统教程中频繁出现的git checkout、git rebase等命令更容易让人望而生畏。事实上&a…...

Pixel-to-Space 像素到空间 一镜到底·跨镜连续技术解析方案

Pixel-to-Space 像素到空间 一镜到底跨镜连续技术解析方案一、技术总览1.1 核心定义Pixel-to-Space像素到空间&#xff0c;是一套自成体系的二维视频像素向三维物理空间实时反演的全域感知范式&#xff0c;跳出市面传统视频解析与空间重建的通用研发路线&#xff0c;形成专属化…...

Cursor Pro破解工具终极指南:5步实现永久免费使用的完整教程

Cursor Pro破解工具终极指南&#xff1a;5步实现永久免费使用的完整教程 【免费下载链接】cursor-free-vip [Support 0.45]&#xff08;Multi Language 多语言&#xff09;自动注册 Cursor Ai &#xff0c;自动重置机器ID &#xff0c; 免费升级使用Pro 功能: Youve reached yo…...