新网银行笔试题 - 分苹果

本文最后更新于:2020年9月6日 下午

题目

小朱有 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)