0

Есть массив из массивов , например такой:

1,1,N
10,13,N
3,N
5,N
N
N
N
12,N
10,13,N
14,N
15,N

То есть в каждом массиве есть в конце null.

Надо выбрать из каждого массива по одному элементу так, чтобы:

  • Все элементы, имеющие значения были упорядочены по возрастанию
  • Количество элементов должно быть наибольшим
  • Сумма разниц между значением элемента и его индексом должна быть наименьшей

То есть в результате должно получиться что то вроде:

1,N,3,5,N,N,N,12,13,14,15

Я реализовал это так. Нашел все варианты, в которых числа идут по порядку, потом выбрал из них лучший (по количеству ненулевых элементов и тд). Все было хорошо, но когда в массиве оказывается 100 по 1-15 элементов в каждом, программа вылетает по таймауту, так и не просчитав все варианты )

2
  • напишите ваш вариант решения, будет понятнее.
    – Romario
    3 апр 2016 в 5:31
  • @Romario, Очень сомневаюсь, там многослойные линки. Да и зачем вам мой вариант? вы свой предложите
    – iRumba
    3 апр 2016 в 5:58

1 ответ 1

1

Первые 2 пункта задача решаются например динамическим программированием + структура данных. Общая идея - создаём дерево (отрезков / Фенвика) которое для i позиции хранит максимальную длину последовательности, оканчивающейся в i и удовлетворяющая пункту 1. Теперь мы берём j строку и перебираем что из неё поставить (какое-либо значение или ничего). Для каждого значения мы берём максимум в дереве от 0 или если есть отрицательные элементы то от -бесконечности до элемента (не включительно как я понял). Сохраняем отдельно. Идём ещё раз по строке j и если значение в дереве соответствующее элементы меньше или равно сохранённому то в дерево на это место сохранённое + 1. Если равно сохранённому +1 то нужно обработать отдельно (в конце опишу). Максимальное значение в дереве и есть ответ на первые 2 пункта.

С 3 пунктом всё не намного сложнее, просто нужно хранить в дереве не только максимум, но и уже посчитанную разность сумм на начальной последовательности, при этом перетирая если значение стало меньше.

Восстановить ответ уже тривиальная задача, можно просто хранить в дереве элемент откуда туда пришли.

Решение не сильно сложное в реализации, но подумать есть над чем, если что непонятно по ответу спрашивайте.

4
  • А как посчитать максимальную длину последовательности, оканчивающуюся в i? ))
    – iRumba
    4 апр 2016 в 15:26
  • мы её не считаем а поддерживаем с помощью дерева.
    – pavel
    4 апр 2016 в 15:29
  • Так... есть массив 8 5 1 6 8 4 3 5 6. Нужно удалить из него минимальное количество элементов, чтобы массив стал упорядоченным. Я не совсем понял как строить эти деревья. Что у нас в данном случае будет в вершине 4 и в вершине 7? Почему?
    – iRumba
    4 апр 2016 в 16:22
  • пошагово [8]=1 [5]=1 [1] = 1 [6]=2 [8]=3 [4]=2 [3]=2 [5]=3 [6]=4
    – pavel
    4 апр 2016 в 17:48

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.