新网银行笔试题 - 分苹果

题目

小朱有 n 个苹果要卖，他有两张桌子 S1，S2 ，要将所有 n 个苹果分别放在两张桌子上，使 S1 上最重的苹果和 S2 上最轻的苹果之差最小。

输入说明：

• 输入数据的组数 t （1行）；
• 第 i 组数据的苹果数量 n （1行 × t）；
• 第 i 组 n 个苹果的重量 n 个整数（1行 × t）；

输出说明：

• t 行，t 组数据的最小值。

输入示例：

5
5
9 9 5 4 8
2
5 9
4
7 2 3 3
4
2 1 8 4
5
1 2 1 3 1

输出示例：

0
4
0
1
0

解题思路

这个题在笔试题里面确实算是简单的，当然可能有更好的解法~

仔细思考一下，其实就是找最小的重量差。翻译为数学问题，任意一组数，只要找到最小差的两个数 a ， b （a <= b），就可以把所有其它小于等于 a 的数分为一组，剩余的大于等于 b 的数分为一组，此时也就满足了一组数的最大值（a）和另一组数的最小值（b）之差最小。

以下代码为一边输入一边就将各组输入数据的结果输出，如果需要计算完所有数据后统一输出，可以将结果暂存到一个列表中。

代码

t = int(input())  # 数据组数
for i in range(t):
    n = int(input())  # 第i组数据的苹果数量n
    weights = [int(item) for item in input().split(' ')]  # 第i组数据n个苹果的重量
    weights.sort()  # 先排序，效率高很多
    m = abs(weights[1] - weights[0])  # 初始化m为任意两苹果的重量差
    for j in range(n - 1):
        tmp = abs(weights[j + 1] - weights[j])
        m = tmp if tmp < m else m  # 更新最小重量差
        if m == 0:
            break  # 0为可能的最小值
    print(m)