刷题笔记合集🔗

剩余银饰的重量

问题描述

有 块二手市场收集的银饰，每块银饰的重量都是正整数，收集到的银饰会被熔化用于打造新的饰品。

每一回合，从中选出三块最重的银饰，然后一起熔掉。

假设银饰的重量分别为 、 和 ，且 。那么熔掉的可能结果如下：

• 如果 ，那么三块银饰都会被完全熔掉；
• 如果 且 ，会剩余重量为 的银块无法被熔掉；
• 如果 且 ，会剩余重量为 的银块无法被熔掉；
• 如果 且 ，会剩余重量为 与 差值的银块无法被熔掉。

最后，

• 如果剩余两块，返回较大的重量（若两块重量相同，返回任意一块皆可）
• 如果只剩下一块，返回该块的重量
• 如果没有剩下，就返回

输入格式

输入数据为两行：

• 第一行为银饰数组长度 ，，
• 第二行为 块银饰的重量，重量的取值范围为 ，重量之间使用空格隔开。

输出格式

如果剩余两块，返回较大的重量（若两块重量相同，返回任意一块皆可）；

如果只剩下一块，返回该块的重量；

如果没有剩下，就返回 。

样例输入

3
1 1 1

3
3 7 10

样例输出

0

1

数据范围

题解

这道题目本质上是一个模拟题，需要按照题目给定的规则一步步处理银饰的熔化过程，直到不能继续为止。

处理逻辑：

1. 将所有银饰按重量排序
2. 每次取出三块最重的银饰，根据它们的关系计算熔化后剩余的银饰重量
3. 如果有剩余，将剩余的银饰插入到已排序的数组中适当的位置
4. 重复上述过程，直到剩余银饰数量小于3

当银饰数量少于3时，根据题目要求输出结果：

• 如果剩余2块，返回较大的那块重量
• 如果剩余1块，返回其重量
• 如果没有剩余，返回0

这道题的关键在于理解熔化规则，尤其是最后一种情况：当三块银饰的重量都不相等时，剩余的银饰重量是两个差值的绝对差。举例来说，如果三块银饰重量为3、7、10，那么7-3=4，10-7=3，|4-3|=1，所以剩余银饰重量为1。

在实现上，时间复杂度主要取决于熔化的回合数。每回合我们要从数组中取出三个元素，并可能插入一个元素。假设最初有n个银饰，那么最多会进行⌊n/2⌋次熔化操作，因此时间复杂度大约为O(n²)，因为每次插入操作最坏情况下需要O(n)时间。对于题目给定的n≤40的范围，这个复杂度是完全可以接受的。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入
n = int(input())
weights = list(map(int, input().split()))

# 对银饰重量进行升序排序
weights.sort()

# 二分查找函数，用于找到合适的插入位置
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    # 返回应该插入的位置
    return left

# 处理熔化过程
while len(weights) >= 3:
    # 取出最重的三块银饰
    z = weights.pop()
    y = weights.pop()
    x = weights.pop()
    
    # 计算熔化后剩余的银饰重量
    remain = abs((z - y) - (y - x))
    
    # 如果有剩余，将其插入到已排序的weights