Модификация алгоритма выбора для выбора взвешенных предметов

Question

Я пытаюсь изменить алгоритм выбора для работы в следующей ситуации:

Мой вывод - список чисел x1, x2, ..., xn (не обязательно упорядоченный).

Каждое из этих чисел имеет вес "w". Я называю W суммой всех весов.

Если я предоставлю значение X, которое больше 0, но не больше W, как я могу найти xi, такое, что сумма весов всех x с индексом больше, чем i, меньше X, и xi's вес + сумма весов всех предметов с индексом больше, чем я, больше или равно X.

Это легко сделать, если мы отсортируем все x по их индексу, но я хочу сделать это без сортировки.

Answer 1

Вам не нужно сортировать их, если вам присвоен идентификатор i. Звучит так, будто вы хотите, чтобы они были в порядке их идентификаторов, которые известны, поэтому вам просто нужно сделать один проход по списку O (n), чтобы привести их в порядок. Затем следуйте одному из опубликованных решений, чтобы выяснить правильное значение i. Я неправильно понимаю проблему?

Обновление

Допустим, у вас есть четыре значения, идентификаторы такие:

[ x4, x1, x3, x2 ]

И их вес соответственно:

[ 14, 10, 5, 19 ]

Все, что вам нужно сделать, это сначала привести списки в порядок. Это не то же самое, что сортировка, потому что в этом случае у вас есть x1 .. xn, где все числа смежны без повторов и т. Д. Таким образом, вы знаете, что результатом будет новый список размером 4.

Сделайте один проход через первый список. В этом случае первое число имеет идентификатор 4, поэтому поместите его в новый список в положение 4 и поместите первый вес в новый список весов также в положение 4. Далее будет помещено в положение 1, и так далее, и так далее четвёртый.

После этого прохода ваши списки будут выглядеть так:

[ x1, x2, x3, x4 ] and [ 10, 19, 5, 14]

Итак, теперь у вас есть заказ, который вы хотите. На этом этапе становится легко просто начать с конца списка весов и найти свойство, которое вы ищете, не более чем с одним обходом списка.

Таким образом, это должно быть O (n).