剩余银饰的重量 - 华为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

题解

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

解题思路

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加群”

🙏整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏