在数组元素上执行操作后获取最小可能数

Question

问:给定一个整数(N)表示编号。初始粒子的数量

给定这些粒子的大小数组

这些粒子可以进行任意数量的模拟(可能没有)。

在一个模拟中，两个粒子结合在一起给出另一个粒子，其大小是它们之间的大小之差(可能是0)。

找到可以形成的最小粒子。

constraints         
n<=1000        
size<=1e9   

Example 1    
3       
30 10 8            
Output           
2         
Explaination- 10 - 8 is the smallest we can achive

Example 2         
4        
1 2 4 8           
output            
1           
explanation            
We cannot make another 1 so as to get 0 so smallest without any simulation is 1

example 3         
5         
30 27 26 10 6         
output
0          
30-26=4            
10-6 =4          
4-4 =0    

我的想法是:我只能想到暴力解决方案，这显然会超时。有没有人能帮我解决这个问题呢？我认为这与动态编程有关

Answer 1

我认为这可以在O(n^2log(n))中解决

考虑您的第三个示例：30 27 26 10 6

对输入进行排序以使其生效：6 10 26 27 30

建立每种(i,j)组合的差异列表。

适用于：

i = 1 -> 4 20 21 24

i = 2 -> 16, 17, 20

i = 3 -> 1, 4

i = 4 -> 3

为什么没有i = 5的列表？因为之前已经考虑过与其他粒子结合。

现在考虑以下情况：

案例1

粒子i尚未与任何其他粒子组合。这意味着其他某个粒子应该已与i以外的其他粒子组合。这表明我们需要在列表j = 1 to N中搜索除j = i之外的A[i]。获取最接近的值。这可以使用二进制搜索来完成。因为您的差异列表已排序！那么你现在的结果是|A[i] - NearestValueFound|

案例2

粒子i与其他一些粒子组合在一起。以上面的i = 1为例，让我们考虑一下它与粒子2的组合。结果是4。所以在除list 2之外的所有列表中搜索4 -因为我们认为粒子2已经与粒子1组合在一起，我们不应该搜索list 2。我们有最好的组合吗？似乎我们在列表3中找到了匹配的4。它不需要是0 -在本例中它是0，所以只需返回0即可。

对所有粒子重复情况1、2。时间复杂度是O(n^2log(n))，因为您正在对除列表i之外的每个i的所有列表进行二进制搜索。

Answer 2

import itertools as it

N = int(input())

nums = list()

for i in range(N):
    nums.append(int(input()))

_min = min(nums)

def go(li):
    global _min
    if len(li)>1:
        for i in it.combinations(li, 2):
            temp = abs(i[0] - i[1])
            if _min > temp:
                _min = temp
            k = li.copy()
            k.remove(i[0])
            k.remove(i[1])
            k.append(temp)
            go(k)

go(nums)

print(_min)