【华为OD】2024D卷——剩余银饰的重量

本文主要是介绍【华为OD】2024D卷——剩余银饰的重量，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：
有N块二手市场收集的银饰，每块银饰的重量都是正整数，收集到的银饰会被熔化用于打造新的饰品。
每一回合，从中选出三块最重的银饰，然后一起熔掉。
假设银饰的重量分别为x、y和z，且x<=y<=z。那么熔掉的可能结果如F:
如果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、将n块重量排序

2、每次取三个元素，按照题目计算剩余重量

3、将剩余重量加入数组，重新排序，执行第2步

上面依然按照数组思路处理；可以换种方法，使用大顶堆来处理n块银饰：

1、每轮判断先heappop()三次，取出x、y、z值，再计算剩余重量

2、直接将剩余重量heappush()到大顶堆中，再重新执行步骤1即可，简化了排序处理过程

---

import heapq
class Solution:#大顶堆def left_weight(self, nums, n):max_heapq = [-w for w in nums]heapq.heapify(max_heapq)while len(max_heapq) >= 3:z = -heapq.heappop(max_heapq)y = -heapq.heappop(max_heapq)x = -heapq.heappop(max_heapq)if x == y == z:continueelif x == y:remaining = z - yelif y == z:remaining = y - xelse:remaining = z - y - (y - x)if remaining > 0:heapq.heappush(max_heapq, -remaining)if max_heapq:return -max_heapq[0]else:return 0# 暴力解法def left_weight_I(self, nums, n):nums_sort = sorted(nums)while len(nums_sort) >= 3:x = nums_sort.pop()y = nums_sort.pop()z = nums_sort.pop()if x == y == z:continueelif x == y:remaining = z - yelif y == z:remaining = y - xelse:remaining = z - y - (y - x)if remaining > 0:nums_sort.append(remaining)nums_sort = sorted(nums_sort)if nums_sort:return nums_sort[-1]else:return 0if __name__ == '__main__':n = int(input())nums = list(map(int, input().split()))solution = Solution()result = solution.left_weight_I(nums, n)print(result)

---

拓展：heapq实现大顶堆

heapq模块常用方法，可见博文

【python笔记】deque()、list()、heapq主要区别-CSDN博客

由于heapq默认实现小顶堆，那么heapq创建一个大顶堆，

1、先将列表中的每个元素取反（即乘以 -1），

2、然后使用 heapq.heapify() 来创建一个最小堆。

3、最小堆的顶部（即根节点）将是原列表中最大的负数，即原列表中最小的元素的相反数。

值得注意的是，在后续操作中，当需要访问或修改堆时，记得对值进行取反操作。

#直接使用方法新建大顶堆import heapq#列表转为大顶堆
max_heapq = [-num for num in nums]
heapq.heapify(max_heapq)#按值压入堆元素val
max_heapq = []
heapq.heappush(max_heapq, -val)#重写新的大顶堆
class MaxHeap:#初始化小顶堆def __init__(self):self.heap = []#按值压入堆元素def push(self, val):heapq.heappush(self.heap, -val)#推出最小堆值，值取反，堆顶值def pop(self):return -heapq.heappop(self.heap)#最小值取反，表示最大值def peek(self):return -self.heap[0]#返回堆大小def size(self):return len(self.heap)

---

知识点：数组、堆

---

结语：越简单的题目解法应该越多，请路过大神留下新的思路供本小白学习一下，打开思路

这篇关于【华为OD】2024D卷——剩余银饰的重量的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---