剩余银饰的重量 - 华为OD统一考试（C卷）

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