剩余银饰的重量 - 华为OD统一考试
OD统一考试(C卷)
分值: 100分
题解: Java / Python / C++
题目描述
有N块二手市场收集的银饰,每块银饰的重量都是正整数,收集到的银饰会被熔化用于打造新的饰品。
每一回合,从中选出三块 最重的 银饰,然后一起熔掉。
假设银饰的重量分别为 x 、y和z,且 x <= y <= z。那么熔掉的可能结果如下:
- 如果 x == y == z,那么三块银饰都会被完全熔掉;
- 如果 x == y 且 y != z,会剩余重量为 z - y 的银块无法被熔掉;
- 如果 x != y 且 y == z,会剩余重量为 y - x 的银块无法被熔掉;
- 如果 x != y 且 y != z,会剩余重量为 z - y 与 y - x 差值 的银块无法被熔掉。
- 最后,如果剩余两块,返回较大的重量(若两块重量相同,返回任意一块皆可);
- 如果只剩下一块,返回该块的重量;如果没有剩下,就返回 0。
输入描述
输入数据为两行
第一行为银饰数组长度 n,1 ≤ n ≤ 40,
第二行为n块银饰的重量,重量的取值范围为[1,2000],重量之间使用空格隔开
输出描述
如果剩余两块,返回较大的重量(若两块重量相同,返回任意一块皆可);
如果只剩下一块,返回该块的重量;如果没有剩下,就返回 0。
示例1
输入:
3
1 1 1输出:
0说明:
选出1 1 1,得到 0,最终数组转换为 [],最后没有剩下银块,返回0
示例2
输入:
3
3 7 10输出:
1说明:
选出 3 7 10,需要计算 (7-3) 和 (10-7) 的差值,即(7-3)-(10-7)=1,所以数组转换为 [1],剩余一块,返回该块重量,返回1
题解
这道题目属于贪心算法的范畴,通过每一轮选择最重的三块银饰进行熔化,根据题目规则计算剩余银块的重量,并不断重复这个过程,直到没有银块为止。在这个过程中,需要注意每一轮熔化的计算方式,以及处理剩余银块的规则。
解题思路
- 使用一个最大堆(或最小堆,但在 Python 中需要对元素取反以实现最大堆的效果)来存储银饰的重量,保证每次选择的都是最重的三块银饰。
- 每次从堆中取出三块银饰,根据题目规则计算剩余银块的重量,并将结果重新放入堆中。
- 不断重复上述步骤,直到堆中银饰数量小于3个。
- 根据题目要求,返回最后剩余的银块重量。
Java
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;
/*** @author code5bug*/
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());for (int i = 0; i < n; i++) {pq.offer(in.nextInt());}Solution solution = new Solution();System.out.println(solution.solve(pq));}
}class Solution {public int solve(PriorityQueue<Integer> pq) {if (pq.isEmpty()) {return 0;} else if (pq.size() == 1) {return pq.peek();} else if (pq.size() == 2) {return Math.max(pq.poll(), pq.poll());}int z = pq.poll(), y = pq.poll(), x = pq.poll();if (x == y && y == z) { // 全部融化} else if (x == y && y != z) {pq.offer(z - y);} else if (x != y && y == z) {pq.offer(y - x);} else {pq.offer(Math.abs((z - y) - (y - x)));}return solve(pq);}
}
Python
import heapqclass Solution:def solve(self, pq):if not pq:return 0elif len(pq) == 1:return pq[0]elif len(pq) == 2:return min(heapq.heappop(pq), heapq.heappop(pq))z = heapq.heappop(pq)y = heapq.heappop(pq)x = heapq.heappop(pq)if x == y and y == z: # 全部融化passelif x == y and y != z:heapq.heappush(pq, -abs(z - y))elif x != y and y == z:heapq.heappush(pq, -abs(y - x))else:heapq.heappush(pq, -abs((z - y) - (y - x)))return self.solve(pq)def main():n = int(input())pq = []for v in map(int, input().split()):heapq.heappush(pq, -v)solution = Solution()print(-solution.solve(pq))if __name__ == "__main__":main()
Python中没有大顶堆的实现。所以元素值进入时讲符号置反以达到想要的大顶堆的作用(最终输出结果时,再转回来)。
C++
#include <iostream>
#include <queue>
#include <functional>using namespace std;class Solution {
public:int solve(priority_queue<int>& pq) {if (pq.empty()) {return 0;} else if (pq.size() == 1) {return pq.top();} else if (pq.size() == 2) {int x = pq.top(); pq.pop();int y = pq.top(); pq.pop();return max(x, y);}int x = pq.top(); pq.pop();int y = pq.top(); pq.pop();int z = pq.top(); pq.pop();if (x == y && y == z) { // 全部融化} else if (x == y && y != z) {pq.push(z - y);} else if (x != y && y == z) {pq.push(y - x);} else {pq.push(abs((z - y) - (y - x)));}return solve(pq);}
};int main() {int n;cin >> n;priority_queue<int> pq;for (int i = 0; i < n; i++) {int temp;cin >> temp;pq.push(temp);}Solution solution;cout << solution.solve(pq) << endl;return 0;
}
❤️华为OD机试面试交流群(每日真题分享): 加V时备注“华为od加群”
🙏整理题解不易, 如果有帮助到您,请给点个赞 ❤️ 和收藏 ⭐,让更多的人看到。🙏🙏🙏
相关文章:

剩余银饰的重量 - 华为OD统一考试
OD统一考试(C卷) 分值: 100分 题解: Java / Python / C 题目描述 有N块二手市场收集的银饰,每块银饰的重量都是正整数,收集到的银饰会被熔化用于打造新的饰品。 每一回合,从中选出三块 最重的…...

redis远程连接不上解决办法
问题描述: redis远程服务端运行在192.168.3.90计算机上,客户端计算机(ip:192.168.3.110)通过redsi-cli.exe客户端工具连接时,没有反应,连接不上。 如图所示: 解决步骤: 步骤一&…...

利用Anaconda安装pytorch和paddle深度学习环境+pycharm安装后不能调用pytorch和paddlepaddle框架
问题现象: 之前安装后不能在添加pytorch和paddlepaddle框架 原因(疑似): 在终端中显示pytorch和paddle在C盘但是安装是安装在J盘 解决办法: 卸载、删除文件重新安装后可以看到文件位置在J盘中 但是选择时还是显示C…...

Eclipses安装教程
一、下载开发工具包 1、开发工具包JDK 下载地址链接:https://www.oracle.com/cn/java/technologies/downloads/ 下载教程: 1)点击链接,可以跳转到页面 2)下滑页面,找到开发工具包 3) 记住下载之…...
安装python版opencv的一些问题
安装python版opencv的一些问题 OpenCV是知名的开源计算机视觉算法库,提供了C\Python\Java版共享库。 在Python中使用OpenCV格外简单,一句命令就能安装,一行import就能引入,可谓是神器。然而,在实际使用中可能遇到一些…...

RabbitMQ入门实战
RabbitMQ 是一个开源的消息中间件,实现了高级消息队列协议(AMQP),用于在分布式系统中进行消息传递。它能够在应用之间传递消息,解耦应用组件,提高系统的可伸缩性和可维护性。RabbitMQ 使用高级消息队列协议…...

vue3-模版引用ref
1. 介绍 概念:通过 ref标识 获取真实的 dom对象或者组件实例对象 2. 基本使用 实现步骤: 调用ref函数生成一个ref对象 通过ref标识绑定ref对象到标签 代码如下: 父组件: <script setup> import { onMounted, ref } …...
C# 十大排序算法
以下是常见的十大排序算法(按照学习和实现的顺序排列): 冒泡排序(Bubble Sort)选择排序(Selection Sort)插入排序(Insertion Sort)希尔排序(Shell Sort&…...

面试之Glide如何绑定Activity的生命周期
Glide绑定Activity生命周期 Glide.with() 下面都是它的重载方法,Context,Activity,FragmentActivity, Fragment, android.app.Fragment fragment,View都可以作为他的参数,内容大同小异,都是先getRetriever࿰…...

从 fatal 错误到 sync.Map:Go中 Map 的并发策略
为什么 Go 语言在多个 goroutine 同时访问和修改同一个 map 时,会报出 fatal 错误而不是 panic?我们该如何应对 map 的数据竞争问题呢? 这篇文章将带你一步步了解背后的原理,并引出解决 map 并发问题的方案。 Map 数据竞争 首先…...
Simon算法详解
0.0 Intro 相关的算法: Deutsh-Jozsa算法: 第一个量子算法对经典算法取得指数级加速的算法 美中不足在于只能确定函数是平衡的还是非平衡的,无法确定函数具体的内容,即无法直接解出函数 Bernstein-Vazirani算法ÿ…...

jrebel IDEA 热部署
1 下载 2022.4.1 JRebel and XRebel - IntelliJ IDEs Plugin | Marketplace 2 选择下载好的zip 离线安装IDEA 插件 重启IDEA 3 打开 [Preference -> JRebel & XRebel] 菜单,输入 GUID address 为 https://jrebel.qekang.com/1e67ec1b-122f-4708-87d…...
pdf拆分成各个小pdf的方法
背景:由于某些缘故,一个大的pdf需要拆分成页数少的pdf,或者pdf需要去掉指定页,那么就有必要对pdf进行重新编辑,这里需要用到一个库,直接进行操作即可。 当使用Python时,可以使用PyMuPDF库来拆分PDF文件。以下是一个示例代码, import fitz # PyMuPDF def split_pdf(i…...

IntelliJ IDEA 常用快捷键一览表(通用型,提高编写速度,类结构、查找和查看源码,替换与关闭,调整格式)
文章目录 IntelliJ IDEA 常用快捷键一览表1-IDEA的日常快捷键第1组:通用型第2组:提高编写速度(上)第3组:提高编写速度(下)第4组:类结构、查找和查看源码第5组:查找、替换…...

MSVS C# Matlab的混合编程系列2 - 构建一个复杂(含多个M文件)的动态库:
前言: 本节我们尝试将一个有很多函数和文件的Matlab算法文件集成到C#的项目里面。 本文缩语: MT = Matlab 问题提出: 1 我们有一个比较复杂的Matlab文件: 这个MATLAB的算法,写了很多的算法函数在其他的M文件里面,这样,前面博客的方法就不够用了。会报错: 解决办法如下…...

上位机图像处理和嵌入式模块部署(qt图像处理)
【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing 163.com】 很多人一想到图像处理,本能的第一反应就是opencv,这也没有错。但是呢,这里面还是有一个问题的,不知…...

AI教我学编程之C#类的实例化与访问修饰符
前言 在这篇文章中,我将带大家深入了解C#编程语言的核心概念,包括类的实例化、访问修饰符的应用,以及C#中不同数据类型的默认值。我会通过逐步分析和具体实例,详细解释如何在C#中正确创建和操作对象,并探讨如何通过访…...

【笔记】Blender4.0建模入门-3物体的基本操作
Blender入门 ——邵发 3.1 物体的移动 演示: 1、选中一个物体 2、选中移动工具 3、移动 - 沿坐标轴移动 - 在坐标平面内移动 - 自由移动(不好控制) 选中物体:右上的大纲窗口,点击物体名称,物体的轮…...

一文详解 Berachain 测试网:全面介绍与教程,bitget wallet教程
什么是Berachain? Berachain(web3.bitget.com/zh-CN/assets/berachain-wallet)是一种尖端区块链技术,使用 Cosmos SDK 构建的 Layer-1,兼容以太坊虚拟机(EVM)。它基于一种独特的概念,…...

小程序使用echarts图表-雷达图
本文介绍下小程序中如何使用echarts 如果是通过npm安装,这样是全部安装的,体积有点大 我这边是使用echarts中的一个组件来实现的,下边是具体流程,实际效果是没有外边的红色边框的,加红色边框的效果是这篇说明 1.echa…...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

深度学习在微纳光子学中的应用
深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...

Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

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

el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)
题目 做法 启动靶机,点进去 点进去 查看URL,有 ?fileflag.php说明存在文件包含,原理是php://filter 协议 当它与包含函数结合时,php://filter流会被当作php文件执行。 用php://filter加编码,能让PHP把文件内容…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)
macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 🍺 最新版brew安装慢到怀疑人生?别怕,教你轻松起飞! 最近Homebrew更新至最新版,每次执行 brew 命令时都会自动从官方地址 https://formulae.…...