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

Question

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

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

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

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

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

Answer 1

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

Рассчитать кумулятивные суммы во вспомогательном массиве 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