Разбиение массива с минимальной разницей - PullRequest
Новая
       20

Разбиение массива с минимальной разницей

2 голосов
/ 06 мая 2019

Задан массив A из N целых чисел. Мне нужно найти X таким образом, чтобы разница между следующими 2 значениями (A[1] * A[2] * ... * A[X]) и (A[X+1] * A[X+2] * ... * A[N]) была минимально возможной, т.е. мне нужно минимизировать | (A[1] * A[2] * ... * A[X]) - (A[X+1] * A[X+2] * ... * A[N]) |, и если таких значений несколько, выведите наименьшее.

Ограничения: -

  • 1 <= <code>N <= 10 ^ 5 </p>

  • 1 <= <code>A[i] <= 10 ^ 18. </p>

Я не могу найти подход для эффективного решения этой проблемы. Какой должен быть лучший подход для решения этой проблемы. Есть ли какой-то особый алгоритм для умножения большого количества чисел.

Ответы [ 2 ]

0 голосов
/ 06 мая 2019

Вы можете сделать это за O (n): первый ход - получить произведение всех элементов массива (P) и второй ход - при условии, что в начале левая часть равна единице, а вторая - P, на каждом шаге iумножить влево на X [i] и разделить вправо на X [i].Продолжайте процесс, пока слева не станет меньше, чем справа.

Поскольку у вас большой массив чисел, вам нужно некоторое умножение больших чисел.Так что, может быть, вам лучше перейти к массиву логарифмов A [i], LA [i] и перейти к новым критериям.

Редактировать:

Как уже упоминалось @CiaPan, точность стандартного 64-разрядного десятичного числа недостаточна для выполнения операции регистрации (поскольку значения могут быть до 10^ 18).

Таким образом, чтобы решить эту проблему, вы должны сначала разбить значения исходного массива на пары таким образом: 

s[2*i]   = a[i].toDouble / (10.0^9)
s[2*i+1] = a[i]/s[2*i]

Массив s в два раза длиннее исходного массива a, но его значения не превышают10 ^ 9, так что можно безопасно применить операцию регистрации, затем найти нужный sX для массива s и разделить его на 2, чтобы получить X для массива a.

Логика сверхточности логарифма не требуется.

0 голосов
/ 06 мая 2019

Идея состоит в том, чтобы использовать форму префикса и суффикса.

Let:

  1. pre[i] = A[1] * A[2] * ... A[i] и
  2. suf[i] = A[i] * A[i + 1] * ... A[N]

Вы можете вычислить эти массивы за O (n) время, как:

  • pre[i] = A[i] * pre[i - 1] с pre[1] = A[i] и

  • suf[i] = A[i] * suf[i + 1] с suf[N] = A[n]

Затем выполните итерацию от i = 1 до N и вычислите максимум: 

abs(pre[i] - suf[i + 1])

Обратите внимание, что pre[i] - suf[i + 1]так же, как: 

(A[1] * A[2] * ... * A[i]) - (A[i + 1] * A[i + 2] ... * A[N])

, что именно то, что вы хотите вычислить.

...