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

题目描述

有 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。

用例

题目解析

本题应该只是一道逻辑模拟题。

我们需要每次取出所有银饰中的最重的三个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 差值 的银块无法被熔掉。

这里的规则其实可以总结为一个公式：

Math.abs((z - y) - (y - x))

带入上面x,y,z关系，即可推导出对应结果式。

这里需要注意的是，当 x != y 且 y != z，此时剩余重量为 z - y 与 y - x 差值 的银块，可能是0，即完全融掉的情况。

如果每次还有未熔完的银块，则重新加入到银饰中，然后再取出最重的三个银饰按照上面逻辑处理，直到所有银饰的数量不足三个，结束上面逻辑。

本题数量级不大，因此每次将未熔完的银块重新加入到银饰中后，可以对所有银饰进行重新排序。但是更优的做法是：

我们只对初始所有银饰进行一次升序，之后取出尾部三个最重的银饰，如果有未熔完的银块remain，那么就在剩余银饰（有序的）进行二分查找remain的有序插入位置，进行插入，这样可以提高效率。

关于二分查找有序插入位置可以看：

import Foundation
func ODTest_47() {
    print("输入描述")
    print("第一行为银饰数组长度 n，1 ≤ n ≤ 40，")
    let n = Int(readLine() ?? "") ?? 0
    if n < 1 || n > 40 {
        print("无")
        return
    }
    print("第二行为n块银饰的重量，重量的取值范围为[1，2000]，重量之间使用空格隔开")
    var weigets = (readLine() ?? "").split(separator: " ").map { Int($0) ?? 0 }
    if weigets.first(where: { $0 < 0 || $0 > 2000 }) != nil || n != weigets.count {
        print("无")
        return
    }

    weigets.sort(by: { $0 > $1 })

    while weigets.count >= 3 {
        // 头部三个最大值
        let three = weigets[...2]
        weigets.removeFirst(3)
        // 如果 x == y == z，那么下面公式结果：remain=0, 表示三块银饰完全融掉
        // 如果 x == y && y != z，那么下面公式结果：remain = z - y
        // 如果 x != y && y == z，那么下面公式结果：remain = y - x
        // 如果 x != y && y != z，那么下面公式结果：remain = Math.abs((z - y) - (y - x))
        let weiget = abs((three[0] - three[1]) - (three[1] - three[2]))
        if weiget > 0 {
            // 在有序插入位置插入
            weigets.append(weiget)
            weigets.sort(by: { $0 > $1 })
        }
    }
    print("输出描述")
    // 如果剩余两块，返回较大的重量（若两块重量相同，返回任意一块皆可）；
    // 如果只剩下一块，返回该块的重量；
    // 如果没有剩下，就返回 0。
    print("\(weigets.first ?? 0)")
}