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

13. 郭老师爱合并果子

1 题目描述

郭老师爱合并果子

成绩20开启时间2021年10月8日 星期五 18:00
折扣0.8折扣时间2021年10月26日 星期二 00:00
允许迟交关闭时间2021年12月1日 星期三 00:00

郭老师家有个果园,每年到了秋收的时候都会收获很多不同种类的果子。他决定把所有的果子合成一堆,但由于体力有限,郭老师在每次合并的时候只能将两堆果子合并到一起。假设有 ​ 堆果子,那么经过 ​ 次合并即可完成任务,且消耗的总体力等于每次合并所消耗的体力之和。

因为郭老师还需要保留体力将果子运回家,所以在合并果子过程中要尽可能地节省体力。假定每个果子重量均为​,并且已知果子的种类数和每种果子的数目,你的任务是设计出合理的合并方案,使郭老师耗费的体力最少。

例如有​种果子,数目依次为​。合并方案如下:

  1. ​ 合并,得到新堆数目为​,耗费体力为​。

  1. 将新堆与第三堆合并,又得到新堆,数目为​,耗费的体力为​。

  1. 总共消耗体力为 ​,可以证明​为最小的体力耗费值。

输入格式

输入包括两行,第一行是一个整数 ​,表示果子的种类数。第二行包含 ​ 个整数,用空格分隔,第 ​ 个整数 ​是第 ​ 种果子的数目。

输出

输出包括一行,这一行只包含一个整数,即最小的体力耗费值。


 测试输入 期待的输出 时间限制 内存限制 额外进程
测试用例 1以文本方式显示
  1. 3↵
  2. 1 2 9↵
以文本方式显示
  1. 15↵
1秒1024KB0

2 代码

//小根堆是一种特殊形式的完全二叉树,可以使用数组来存储
//注意其中很巧妙的下标2倍关系
//从1开始存,0号元素不使用,可以很好的利用上下标的2倍关系
#include<stdio.h>
#include<stdlib.h>long int* heap;
long int heapSize = 0;  //堆元素个数
long int sum = 0;void swap(long int* a, long int* b) {long int temp;temp = *a;*a = *b;*b = temp;
}//存入新数,从末尾存,然后排序
void put(long int num) {long now, next;heap[++heapSize] = num;  //初始值是0,使用前自增now = heapSize;while (now > 1) {next = now >> 1;  //位运算,相当于/2,速度更快if (heap[now] >= heap[next])   //符合结构,直接退出,其他地方都是有序的break;swap(&heap[now], &heap[next]);  //没有直接退出,说明需要交换now = next;}
}//弹出表头,只能从头操作,然后把最后一个数放到根的位置上,排序处理
long int pop() {long int now = 1, next, res = heap[1];heap[1] = heap[heapSize];heapSize--;while (now * 2 <= heapSize) {  //保证有左分支next = now * 2;if (next < heapSize && heap[next + 1] < heap[next])  //有右分支,而且右分支比左分支小next++;if (heap[now] <= heap[next])break;  //符合结构,直接退出swap(&heap[now], &heap[next]);  //没有直接退出,说明不符合结构,需要交换now = next;   //传递继续操作}return res; //弹出的数
}int main(int argc, char* argv[]) {//freopen("file in.txt","r",stdin);long int n;long int i;long int temp;scanf("%ld", &n);//根据输入的n的大小来申请空间heap = (long int*)malloc(sizeof(long int) * (n + 1));for (i = 1;i <= n;i++) {scanf("%ld", &heap[i]);put(heap[i]);}//只有一堆果子的情况if (n == 1) {printf("0\n");return 0;}while (n > 1) {temp = pop() + pop();  //这两个pop()可不一样哦sum += temp;put(temp);   //存进去,会自动处理成小根堆n--;}printf("%ld\n", sum);return 0;
}

相关文章:

13. 郭老师爱合并果子

1 题目描述 郭老师爱合并果子成绩20开启时间2021年10月8日 星期五 18:00折扣0.8折扣时间2021年10月26日 星期二 00:00允许迟交否关闭时间2021年12月1日 星期三 00:00 郭老师家有个果园&#xff0c;每年到了秋收的时候都会收获很多不同种类的果子。他决定把所有的果子合成一堆&…...

Method breakpoints may dramatically slow down debugging 解决方案

项目无法启动了 简单介绍一下事情的过程&#xff1a;昨天在进行代码调试的时候&#xff0c;代码部分处理完成之后&#xff0c;启动debug模式的热部署准备测试一下逻辑&#xff0c;结果左下角提示我热部署失败&#xff0c;需要重新启动Tomcat才能再次调试&#xff0c;所以只得重…...

ABAP ALV和OOALV设置单元格颜色,编辑

首先给大家分享一篇博客: REUSE_ALV_GRID_DISPLAY_LVC-可编辑单元格 文章目录单元格编辑单元格/行-颜色效果展示**需求:**我是想实现某个单元格可根据数据来判断是否是可以进行编辑的或要添加一个什么样的颜色. 我们需要用到下面的三个结构 ALV 控制: 单元格的类型表:LVC_T_ST…...

Java知识复习(十三)数据库和SQL

1、主键和外键 主键也叫主码。主键用于唯一标识一个元组&#xff0c;不能有重复&#xff0c;不允许为空。一个表只能有一个主键。外键也叫外码。外键用来和其他表建立联系用&#xff0c;外键是另一表的主键&#xff0c;外键是可以有重复的&#xff0c;可以是空值。一个表可以有…...

JVM虚拟机种类

1,Sun Classic VM: 1.现在此款虚拟机已经淘汰了&#xff0c;是历史上第一款商用的虚拟机。2.只能使用纯解释器的方式来执行Java代码。3.服役于 JDK 1.0、1.1、1.2&#xff1b;在 1.3、1.4 作为 HotSpot VM 的备选 VM&#xff1b;之后退出历史舞台&#xff1b;2,Sun Exact VM 1.…...

Linux操作系统学习(线程基础)

文章目录线程的基础概念线程控制内核LWP和线程ID的关系线程的基础概念 ​ 一般教材对线程描述是&#xff1a;是在进程内部运行的一个分支&#xff08;执行流&#xff09;&#xff0c;属于进程的一部分&#xff0c;粒度要比进程更加细和轻量化 ​ 一个进程中是可能存在多个线程…...

YOLOv5源码逐行超详细注释与解读(1)——项目目录结构解析

前言 前面简单介绍了YOLOv5的网络结构和创新点&#xff08;直通车&#xff1a;【YOLO系列】YOLOv5超详细解读&#xff08;网络详解&#xff09;&#xff09; 在接下来我们会进入到YOLOv5更深一步的学习&#xff0c;首先从源码解读开始。 因为我是纯小白&#xff0c;刚开始下…...

前端开发总结的一些技巧和实用方法(2)

本文主要介绍一些JS中用到的小技巧和实用方法&#xff0c;可以在日常Coding中提升幸福度&#xff0c;也可以通过一些小细节来增加代码可读性&#xff0c;让代码看起来更加优雅&#xff0c;后续将不断更新1.数组 map 的方法 (不使用Array.Map) Array.from 还可以接受第二个参数…...

Docker搭建jenkins(Vue自动化部署)

前言 需要提前准备的条件 Docker环境 一、jenkins镜像 # 查询镜像 docker search jenkins# 下载镜像 # lts稳定版 docker pull jenkins/jenkins:lts#查看镜像 docker images二、启动Jenkins容器 创建挂载文件夹&#xff0c;并且进行文件授予权限 #创建文件夹 mkdir -p /home/j…...

ADCS攻击之CVE-2022–26923

CSDN自动博客文章迁移漏洞简介该漏洞允许低权限用户在安装了 Active Directory 证书服务 (AD CS) 服务器角色的默认 Active Directory 环境中将权限提升到域管理员。在默认安装的ADCS里就启用了Machine模板。漏洞利用添加机器账户&#xff0c;并将该机器账户dnsHostName指向DC[…...

AO3401-ASEMI低压P沟道MOS管AO3401

编辑&#xff1a;ll AO3401-ASEMI低压P沟道MOS管AO3401 型号&#xff1a;AO3401 品牌&#xff1a;ASEMI 封装&#xff1a;SOT-23 最大漏源电流&#xff1a;-4.2A 漏源击穿电压&#xff1a;-30V RDS&#xff08;ON&#xff09;Max&#xff1a;0.05Ω 引脚数量&#xff1…...

【STM32MP157应用编程】3.控制PWM

目录 PWM文件 指令操作PWM 程序操作PWM 程序说明 程序代码 3_PWM_1.c 启动交叉编译工具 编译 拷贝到开发板 测试 PWM文件 在/sys/class/pwm目录下&#xff0c;存放了PWM的文件。 pwmchip0和pwmchip4目录对应了MP157 SoC的2个PWM控制器&#xff0c;pwmchip0对应的是M…...

基于Python的selenium

一、安装 1.1安装Python&#xff0c;安装Python时需要勾选增加环境变量 如果之前已经安装过Python&#xff0c;需要将Python相关文件以及环境变量删除 1.2安装成功&#xff1a;在命令行界面下输入Python&#xff0c;最终展示>>>即可成功 2.1安装pycharm,直接自定义安装…...

Go底层原理:一起来唠唠GMP调度(一)

目录前言一、进程、线程、Goroutine1、进程与线程2、Goroutine二、Go调度器设计思想1、线程模型1.1 内核级线程模型1.2 用户级线程模型1.3 混合型线程模型2、 被废弃的 G-M 调度器2.1 了解 G-M 调度如何工作3、如今高效的 GMP 模型3.1 GMP模型调度流程3.2 GMP调度设计策略3.3 G…...

前端——1.相关概念

这篇文章主要介绍前端入门的相关概念 1.网页 1.1什么是网页&#xff1f; 网站&#xff1a;是指在因特网上根据一定的规则&#xff0c;使用HTML等制作的用于展示特定内容相关的网页集合 网页&#xff1a;是网站中的一“页”&#xff0c;通常是HTML格式的文件&#xff0c;它要…...

java四种线程池(基本使用)

标题java四种线程池及使用示例 1、线程工厂 1、我们先来写ThreadFactory&#xff0c;在创建线程池时候可以传入自定义的线程工厂&#xff0c;线程工厂说白了就是用来定制线程的一些属性&#xff1a;名字、优先级、是否为守护线程。直接看代码即可。 当然创建线程池的时候可以…...

float的表示范围为什么比long大

●很多人会有一个疑问, 一个用来表示小数的 float 为什么表示的范围会比 long 还要大呢 ? ●这次, 咱们就来详细说一说这个事情 从长计议 ●聊到这个话题, 我们就要从计算机存储数字这个位置说起了 ●计算机存储数字的方式其实就是 : 二进制 二进制是计算机中最基本的数字存储…...

Flutter Android 打包保姆式全流程 2023 版

大家好&#xff0c;我是 17。 为什么要写这篇文章呢&#xff1f;对于一没有 android 开发经验&#xff0c;从未有过打包经历的新人来说&#xff0c;要想成功打包&#xff0c;是很困难的。因为受到的阻碍太多&#xff0c;是完全陌生的领域&#xff0c;几乎是寸步难行。如果有老…...

C++笔记之lambda表达式

引言 Lambda表达式是从C 11版本引入的特性&#xff0c;利用它可以很方便的定义匿名函数对象&#xff0c;通常作为回调函数来使用。大家会经常拿它和函数指针&#xff0c;函数符放在一起比较&#xff0c;很多场合下&#xff0c;它们三者都可以替换着用。 语法 [ captures ] (…...

flink大数据处理流式计算详解

flink大数据处理 文章目录flink大数据处理二、WebUI可视化界面&#xff08;测试用&#xff09;三、Flink部署3.1 JobManager3.2 TaskManager3.3 并行度的调整配置3.4 区分 TaskSolt和parallelism并行度配置四、Source Operator(资源算子)五、Sink Operator(输出算子)六、Flink滑…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

Unity VR/MR开发-VR开发与传统3D开发的差异

视频讲解链接&#xff1a;【XR马斯维】VR/MR开发与传统3D开发的差异【UnityVR/MR开发教程--入门】_哔哩哔哩_bilibili...

在golang中如何将已安装的依赖降级处理,比如:将 go-ansible/v2@v2.2.0 更换为 go-ansible/@v1.1.7

在 Go 项目中降级 go-ansible 从 v2.2.0 到 v1.1.7 具体步骤&#xff1a; 第一步&#xff1a; 修改 go.mod 文件 // 原 v2 版本声明 require github.com/apenella/go-ansible/v2 v2.2.0 替换为&#xff1a; // 改为 v…...

C++--string的模拟实现

一,引言 string的模拟实现是只对string对象中给的主要功能经行模拟实现&#xff0c;其目的是加强对string的底层了解&#xff0c;以便于在以后的学习或者工作中更加熟练的使用string。本文中的代码仅供参考并不唯一。 二,默认成员函数 string主要有三个成员变量&#xff0c;…...