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


class Solution:
    def solve(self, pq):
        if not pq:
            return 0
        elif 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:  # 全部融化
            pass
        elif 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加群”

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