Получение минимально возможного числа после выполнения операций над элементами массива

Question

Вопрос. Дано целое число (n), обозначающее «нет». частиц вначале
Учитывая массив размеров этих частиц
Эти частицы могут go участвовать в любом количестве симуляций (возможно, ни одной)
В одном симуляции две частицы объединяются, чтобы дать другую частицу с размером в качестве разности между их размером (возможно 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    

Мое мышление: я могу думать только о грубой силе, которая, очевидно, истечет. Может ли кто-нибудь помочь мне с этим подходом? Я думаю, что это связано с динамическим c программированием

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. Это говорит о том, что нам нужно искать A[i] в списках j = 1 to N, за исключением j = i. Получить ближайшее значение. Это можно сделать с помощью бинарного поиска. Потому что ваши списки различий отсортированы! Тогда ваш результат на данный момент равен |A[i] - NearestValueFound|

Случай 2

Частица i объединена с некоторой другой частицей. Возьмите пример i = 1 выше и давайте рассмотрим, что он объединен с частицей 2. Результат 4. Поэтому ищите 4 во всех списках, кроме списка 2 - потому что мы считаем, что частица 2 уже объединена с частицей 1, и мы не должны искать список 2. У нас есть лучший матч? Кажется, в списке 3 найдено совпадение 4. Это не должно быть 0 - в этом случае это 0, поэтому просто верните 0.

Повторите Случай 1, 2 для всех частиц. Сложность по времени составляет O(n^2log(n)), поскольку вы выполняете двоичный поиск по всем спискам для каждого i, за исключением списка i.