腾讯有趣数字

2022-03-30 17:50 92阅读 0赞

**题目描述**  
小Q今天在上厕所时想到了这个问题：有n个数，两两组成二元组，差的绝对值最小的有多少对呢？差的绝对值最大的呢？  
这么无聊，上厕所想出这么变态的题目。。。。。。。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]

--------------------

## 解题思路 ##

采用暴力的解法

1.  首先对数组进行排序
2.  那么相差最大组的数目就是最大值的个数乘以最小值得个数
3.  遍历数组一次，找出相差最小的值
4.  再遍历一次数组，如果两个值的差等于这个值，那么相差最小的对数加一

需要注意的是：例如3 3 3 2 2，相差为0的元组数目有4对而不是3对

--------------------

## 通过代码 ##

import sys
    def TowTuple(n, a):
        a.sort()
        minA, maxA = 1, 1
        for i in range(1, n):
            if a[i] == a[0]:
                minA += 1
            else:
                break
        for i in range(n - 2, - 1, -1):
            if a[i] == a[n - 1]:
                maxA += 1
            else:
                break
        ans2 = minA * maxA
        minDiffer = 1000000
        ans1 = 0
        for i in range(1, n):  #找出最小差值
            differ = a[i] - a[i - 1]
            if differ < minDiffer:
                minDiffer = differ
        for i in range(0, n):
            for j in range(i + 1, n):
                if a[j] - a[i] == minDiffer:
                    ans1 += 1
                elif a[j] - a[i] > minDiffer:   #超时的举措，将后面的全部掐掉
                    break
        return ans1, ans2
    try:
        while True:
            line1 = sys.stdin.readline().strip()
            line2 = sys.stdin.readline().strip()
            if line1 == '':
                break
            n = int(line1)
            a = list(map(int, line2.split()))
            ans1, ans2 = TowTuple(n, a)
            print(ans1, ans2)
    except:
        pass

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]: /images/20220330/2a315466cb3646d5966d4ea236112ead.png