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

剩余银饰的重量 - 华为OD统一考试

OD统一考试(C卷)

分值: 100分

题解: Java / Python / C++

alt

题目描述

有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

题解

这道题目属于贪心算法的范畴,通过每一轮选择最重的三块银饰进行熔化,根据题目规则计算剩余银块的重量,并不断重复这个过程,直到没有银块为止。在这个过程中,需要注意每一轮熔化的计算方式,以及处理剩余银块的规则。

解题思路

  1. 使用一个最大堆(或最小堆,但在 Python 中需要对元素取反以实现最大堆的效果)来存储银饰的重量,保证每次选择的都是最重的三块银饰。
  2. 每次从堆中取出三块银饰,根据题目规则计算剩余银块的重量,并将结果重新放入堆中。
  3. 不断重复上述步骤,直到堆中银饰数量小于3个。
  4. 根据题目要求,返回最后剩余的银块重量。

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统一考试&#xff08;C卷&#xff09; 分值&#xff1a; 100分 题解&#xff1a; Java / Python / C 题目描述 有N块二手市场收集的银饰&#xff0c;每块银饰的重量都是正整数&#xff0c;收集到的银饰会被熔化用于打造新的饰品。 每一回合&#xff0c;从中选出三块 最重的…...

redis远程连接不上解决办法

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

利用Anaconda安装pytorch和paddle深度学习环境+pycharm安装后不能调用pytorch和paddlepaddle框架

问题现象&#xff1a; 之前安装后不能在添加pytorch和paddlepaddle框架 原因&#xff08;疑似&#xff09;&#xff1a; 在终端中显示pytorch和paddle在C盘但是安装是安装在J盘 解决办法&#xff1a; 卸载、删除文件重新安装后可以看到文件位置在J盘中 但是选择时还是显示C…...

Eclipses安装教程

一、下载开发工具包 1、开发工具包JDK 下载地址链接&#xff1a;https://www.oracle.com/cn/java/technologies/downloads/ 下载教程&#xff1a; 1&#xff09;点击链接&#xff0c;可以跳转到页面 2&#xff09;下滑页面&#xff0c;找到开发工具包 3&#xff09; 记住下载之…...

安装python版opencv的一些问题

安装python版opencv的一些问题 OpenCV是知名的开源计算机视觉算法库&#xff0c;提供了C\Python\Java版共享库。 在Python中使用OpenCV格外简单&#xff0c;一句命令就能安装&#xff0c;一行import就能引入&#xff0c;可谓是神器。然而&#xff0c;在实际使用中可能遇到一些…...

RabbitMQ入门实战

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

vue3-模版引用ref

1. 介绍 概念&#xff1a;通过 ref标识 获取真实的 dom对象或者组件实例对象 2. 基本使用 实现步骤&#xff1a; 调用ref函数生成一个ref对象 通过ref标识绑定ref对象到标签 代码如下&#xff1a; 父组件&#xff1a; <script setup> import { onMounted, ref } …...

C# 十大排序算法

以下是常见的十大排序算法&#xff08;按照学习和实现的顺序排列&#xff09;&#xff1a; 冒泡排序&#xff08;Bubble Sort&#xff09;选择排序&#xff08;Selection Sort&#xff09;插入排序&#xff08;Insertion Sort&#xff09;希尔排序&#xff08;Shell Sort&…...

面试之Glide如何绑定Activity的生命周期

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

从 fatal 错误到 sync.Map:Go中 Map 的并发策略

为什么 Go 语言在多个 goroutine 同时访问和修改同一个 map 时&#xff0c;会报出 fatal 错误而不是 panic&#xff1f;我们该如何应对 map 的数据竞争问题呢&#xff1f; 这篇文章将带你一步步了解背后的原理&#xff0c;并引出解决 map 并发问题的方案。 Map 数据竞争 首先…...

Simon算法详解

0.0 Intro 相关的算法&#xff1a; Deutsh-Jozsa算法&#xff1a; 第一个量子算法对经典算法取得指数级加速的算法 美中不足在于只能确定函数是平衡的还是非平衡的&#xff0c;无法确定函数具体的内容&#xff0c;即无法直接解出函数 Bernstein-Vazirani算法&#xff…...

jrebel IDEA 热部署

1 下载 2022.4.1 JRebel and XRebel - IntelliJ IDEs Plugin | Marketplace 2 选择下载好的zip 离线安装IDEA 插件 重启IDEA 3 打开 [Preference -> JRebel & XRebel] 菜单&#xff0c;输入 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组&#xff1a;通用型第2组&#xff1a;提高编写速度&#xff08;上&#xff09;第3组&#xff1a;提高编写速度&#xff08;下&#xff09;第4组&#xff1a;类结构、查找和查看源码第5组&#xff1a;查找、替换…...

MSVS C# Matlab的混合编程系列2 - 构建一个复杂(含多个M文件)的动态库:

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

上位机图像处理和嵌入式模块部署(qt图像处理)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 很多人一想到图像处理&#xff0c;本能的第一反应就是opencv&#xff0c;这也没有错。但是呢&#xff0c;这里面还是有一个问题的&#xff0c;不知…...

AI教我学编程之C#类的实例化与访问修饰符

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

【笔记】Blender4.0建模入门-3物体的基本操作

Blender入门 ——邵发 3.1 物体的移动 演示&#xff1a; 1、选中一个物体 2、选中移动工具 3、移动 - 沿坐标轴移动 - 在坐标平面内移动 - 自由移动&#xff08;不好控制&#xff09; 选中物体&#xff1a;右上的大纲窗口&#xff0c;点击物体名称&#xff0c;物体的轮…...

一文详解 Berachain 测试网:全面介绍与教程,bitget wallet教程

什么是Berachain&#xff1f; Berachain&#xff08;web3.bitget.com/zh-CN/assets/berachain-wallet&#xff09;是一种尖端区块链技术&#xff0c;使用 Cosmos SDK 构建的 Layer-1&#xff0c;兼容以太坊虚拟机&#xff08;EVM&#xff09;。它基于一种独特的概念&#xff0c…...

小程序使用echarts图表-雷达图

本文介绍下小程序中如何使用echarts 如果是通过npm安装&#xff0c;这样是全部安装的&#xff0c;体积有点大 我这边是使用echarts中的一个组件来实现的&#xff0c;下边是具体流程&#xff0c;实际效果是没有外边的红色边框的&#xff0c;加红色边框的效果是这篇说明 1.echa…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

内存分配函数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&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

Xshell远程连接Kali(默认 | 私钥)Note版

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

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; 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伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)

macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 &#x1f37a; 最新版brew安装慢到怀疑人生&#xff1f;别怕&#xff0c;教你轻松起飞&#xff01; 最近Homebrew更新至最新版&#xff0c;每次执行 brew 命令时都会自动从官方地址 https://formulae.…...