Блог

Главная - Вопросы по программированию - Максимально возможное целое число x, такое, чтобы сумма каждого элемента массива, деленная на x, была не меньше k

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

#arrays #math

#массивы #математика

Вопрос:

Нам дан массив из 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) ?

Комментарии:

1. Существует ли какое-либо ограничение на значения в массиве, хотя бы на порядок величины? В частности, сопоставимы ли они с n ? У меня есть алгоритм с желаемой сложностью, если они имеют тот же порядок, что и n .

2. @RoryDaulton 1<=arr [i]<= 10 ^ 9 , дайте мне ваш алгоритм, он может сработать

Ответ №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 , so N log(M) < 2 N log(N) и ваша желаемая эффективность все еще достигнута. Если N это мало, а M это велико, ваша желаемая эффективность не достигнута. (Это означает массив типа [10^9, 10^9-1] where N = 2 и M = 10^9 который мог бы выполнять 30 шаги в двоичном поиске.) Это может соответствовать или не соответствовать вашим потребностям.