Максимально возможное целое число x, такое, что сумма каждого элемента массива, деленная на x, не меньше k

Question

Нам дан массив из n целых чисел и постоянное значение k, может ли кто-нибудь предложить мне найти максимально возможное целое число x такое, что arr [0] / x + arr [1] / x +.. arr [n-1] / x> = k,

-> where '/' is the integer division 
-> sum of all elements of array >= k
-> k is a constant(1<=k<=10^5)
-> 1<=n<=10^5.
e.g. n=5, k=3
arr=[1,1,1,8,8]
answer-> x=4
in something like o(N log N) ?

Answer 1

Вот алгоритм, который часто соответствует вашим ограничениям по времени.Я предполагаю, что ваши значения массива неотрицательны.Алгоритм зависит от этих фактов:

1. Ваша целевая функция arr[0]/x + arr[1]/x +.. arr[n-1]/x (назовем ее f(x)) - это убывающая функция x.Другими словами, если x увеличивается, то f(x) останется прежним или уменьшится.
2. f(1) равно сумме элементов массива, поэтому f(1) >= k.Другими словами, на x = 1 целевая функция не ниже целевого значения k.
3. Если для M установлено максимальное значение массива, значение arr[i] // (M + 1) равно нулю, поэтому f(M + 1) = 0.Другими словами, на x = M + 1 цель находится ниже целевого значения k.

Таким образом, у нас есть верхняя и нижняя границы значения x для убывающей функции.Поэтому мы можем выполнить бинарный поиск от 1 до M + 1 для значения x, где

f(x) >= k and f(x + 1) < k

Это будет удовлетворять только одно значение x, и бинарный поиск может легко найтиЭто.Бинарный поиск займет log(M) шагов.Каждый шаг включает в себя одну оценку f(x), которая использует N шагов для использования каждого члена массива.Таким образом, общая эффективность времени составляет O(N log(M)).Если M (максимальное значение массива) имеет порядок N, тогда это ваша желаемая эффективность.При заданных вами предельных значениях для N и значениях массива у нас есть M < N^2, поэтому N log(M) < 2 N log(N) и ваша желаемая эффективность все еще достигается.Если N мало, а M велико, желаемая эффективность не достигается.(Это означает массив типа [10^9, 10^9-1], где N = 2 и M = 10^9, который может выполнить 30 шагов в бинарном поиске.) Это может или не может удовлетворить ваши потребности.