剩余银饰的重量 - 华为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…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...

高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...
【Go语言基础【13】】函数、闭包、方法
文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数(函数作为参数、返回值) 三、匿名函数与闭包1. 匿名函数(Lambda函…...

Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...

并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...