Нахождение порогового значения в данном массиве - PullRequest
Новая
       15

Нахождение порогового значения в данном массиве

0 голосов
/ 26 февраля 2019

Учитывая массив, я должен найти максимальное пороговое значение, чтобы элементы, меньшие, чем в массиве, умножались на c1 и больше, чем умноженные на c2.

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

Я думал об использовании BST.Я не мог придумать ни одной идеи.Можете ли вы помочь мне в эффективном алгоритме?

Пример: 400, 500, 600 с1 = 0,05 с2 = 0,1 Значение: 125

Здесь пороговое значение равно 500. (500 + 600)* 0,1 + 400 * 0,05 = 130

1 Ответ

0 голосов
/ 26 февраля 2019

Если элементы положительные (или, по крайней мере, кумулятивные суммы являются монотонными), вы можете применить бинарный поиск:

Рассчитать кумулятивные суммы во вспомогательном массиве Sums[]

При бинарном поиске найдите наименьшееиндекс k (например, std::lower_bound в C ++ STL), что 

 Sums[k] * c1 + (OverallSum - Sums[k]) * c2 >= Value
 or 
 Sums[k]  >= (Value - OverallSum * c2) / (c1 - c2)

Обратите внимание, что первый этап занимает время O (n), поэтому для одноразового задания вы можете использовать простой линейный поиск на второмэтап.

Но если вы повторно используете один и тот же массив с разными Value - бинарный поиск будет более эффективным.

Здесь 

Sums = [400, 900, 1500]
(Value - OverallSum * c2) / (c1 - c2) = 
   (125 - 1500 * 0.1) / (0.05-0.1) = 
      -25 / -0.05 = 500

 The first value in Sums[] > 500 is 900, so index is 1, value is 500
...