Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
trympyrym
0 / 0 / 0
Регистрация: 13.08.2013
Сообщений: 17
1

Выбрать из заданного массива элементов набор длины k, обеспечивающий минимум f(i, j)

11.10.2013, 00:43. Просмотров 360. Ответов 5
Метки нет (Все метки)

Задача такая: дан массив длины n. Известна функция f(i, j), определенная на парах элементов этого массива (i ≠ j). Значения функции уже вычислены для всех пар. Требуется найти такой набор элементов K (длины k), в котором максимальное (по всем i, j из K) значение функции f минимально среди всех наборов длины k.

Наглядный пример с точками для лучшего понимания условия в спойлере
Кликните здесь для просмотра всего текста
Пусть есть n точек на прямой. За f(i, j) обозначим расстояние между точками i и j. В таком случае требуется найти такой набор из k точек, в котором расстояние между двумя его наиболее удаленными точками минимально. (например для массива точек {-3, -1, 0, 1, 3} длины n=5 и k = 3 ответ будет {-1, 0, 1} )


Крайне желательно решить эту задачу за O(n2)
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.10.2013, 00:43
Ответы с готовыми решениями:

Разработать класс, набор методов (конструктор и минимум два метода) для программной модели заданного объекта
Разработать класс, набор методов (конструктор и минимум два метода) для...

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

Выбрать из заданного текста слова заданной длины
Доброго времени суток,народ) Прошу помочь с такой задачей: Выбрать из...

Выбрать из заданного текста слова заданной длины и напечатать их по одному на каждой строке
Выбрать из заданного текста слова заданной длины и напечатать их по одному на...

Из элементов массива А длины 2N получить массивы В и С длины N указанным способом
Из элементов массива А длины 2N получить массивы В и С длины N каждый следующим...

5
Qwertiy
821 / 629 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
11.10.2013, 13:45 2
Дан массив f[n][n], надо найти массив индексов i[k] так, чтобы max {q in i, w in i} of f[q][w] был минимально возможным, верно? Или надо найти цельный подмассив размера k*k?
0
trympyrym
0 / 0 / 0
Регистрация: 13.08.2013
Сообщений: 17
11.10.2013, 13:48  [ТС] 3
Цитата Сообщение от Qwertiy Посмотреть сообщение
Дан массив f[n][n], надо найти массив индексов i[k] так, чтобы max {q in i, w in i} of f[q][w] был минимально возможным
Именно так
0
salam
176 / 157 / 29
Регистрация: 10.07.2012
Сообщений: 769
12.10.2013, 09:39 4
можно решить за O(nk) <= O(n*n), если считать ручками, за O(nlogn), если максимумы на отрезках считать деревом отрезков. Счиаем для каждой точки максимум на отрезке с началом в ней.
0
trympyrym
0 / 0 / 0
Регистрация: 13.08.2013
Сообщений: 17
12.10.2013, 12:22  [ТС] 5
Если можно, чуть подробнее.

А именно: что значит "считать ручками" и что значит "максимум на отрезке"

Первое мое знакомство с деревом отрезков привело к сомнениям, что мою задачу можно этим методом решить за nlogn.
Как "считать ручками" за nk у меня чтой-то совсем никаких мыслей нет

ЗЫ. дерево отрезков, как я понял, может за logN найти некую функцию на отрезке (например {1, 2,3 }). В моем же случае необходимый минимум может дать набор {1, 12, 156}
0
salam
176 / 157 / 29
Регистрация: 10.07.2012
Сообщений: 769
12.10.2013, 15:59 6
Цитата Сообщение от trympyrym Посмотреть сообщение
Если можно, чуть подробнее.

А именно: что значит "считать ручками" и что значит "максимум на отрезке"

Первое мое знакомство с деревом отрезков привело к сомнениям, что мою задачу можно этим методом решить за nlogn.
Как "считать ручками" за nk у меня чтой-то совсем никаких мыслей нет

ЗЫ. дерево отрезков, как я понял, может за logN найти некую функцию на отрезке (например {1, 2,3 }). В моем же случае необходимый минимум может дать набор {1, 12, 156}
Прошу прощения, я почему-то решил, что надо выбрать к последовательных элементов.
0
12.10.2013, 15:59
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.10.2013, 15:59

Дан набор из N отрезков различной длины.Сколькими способами можно выбрать из этих отрезков три,из которых можно составить треугольник?
Дан набор из N отрезков различной длины.Сколькими способами можно выбрать из...

Найти произведение элементов и минимум элементов, расположенных между главной и побочной диагональю выше середины массива
В данном двумерном квадратном массиве найдите произведение элементов и минимум...

Машина Поста: вычислить остаток от деления длины заданного массива на 5.
На ленте задан массив. Вычислить остаток от деления длины заданного массива на...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru