с# - Помощь студентам

22hope22 · 27.05.2013, 23:52

Помогите, пожалуйста, с задачей для курсовой

Вpемя pазбpасывать камни и вpемя соpтиpовать камни…
В одном уездном гоpоде есть старое забpошенное кладбище. Оно пpедставляет собой длинный унылый pяд безымянных надгpобий в виде камней pазной фоpмы. Вес всех камней pазный. Решили привести погост в порядок, отсортировав надгpобные камни по весу. Местный обычай позволяет менять два камня местами, если между ними находится ровно K дpугих камней.

Исходные данные
В пеpвой стpоке находится целое число N, количество камней (1 ≤ N ≤ 130000). Каждая из следующих N стpок содеpжит целое число X, вес очеpедного камня в гpаммах (1 ≤ X ≤ 130000).
Результат

Должен содеpжать единственное целое число — максимальное значение K (0 ≤ K < N), которое обеспечивает возможность произвести сортировку камней по весу.

Пример
исходные данные
5
30
21
56
40
17
результат
1

eval · 28.05.2013, 00:21

вы сюда решили весь сборник переписать?

22hope22 · 28.05.2013, 15:20

Ха ха ха. Прям юморист

eval · 28.05.2013, 15:24

какое слово рассмешило?

Rififi · 28.05.2013, 15:29

22hope22

Помогите, пожалуйста, с задачей для курсовой

в чем помочь, не вижу ни одного заданного вопроса, просто вываленное задание и всё.

Abstraction · 28.05.2013, 15:54

Кстати, интересная задачка. Я даже за O(N^2) сходу не вижу решения.

BDA · 28.05.2013, 16:19

Мысли вслух:
Считать данные в массив
Отсортировать по возрастанию
Бинарным поиском по второму массиву искать все элементы из первого массива (их новую позицию)
Искать наибольший общий делитель между всеми разницами (новой и старой) в позициях (кроме 0, т.е. камень остался на месте)

Средняя сложность: NlogN + NlogN/log2 + (N-1)*(сложность поиска НОД)

Насколько верны рассуждения не знаю.

Abstraction · 28.05.2013, 16:25

Цитата:

Бинарным поиском по второму массиву искать все элементы из первого массива (их новую позицию)

Плохая новость: веса разных камней могут быть одинаковыми.

BDA · 28.05.2013, 16:37

Цитата:

Сообщение от Abstraction

Плохая новость: веса разных камней могут быть одинаковыми.

Хорошая новость - "Вес всех камней pазный." (из условия)

Abstraction · 28.05.2013, 16:40

А. Оказывается, читать условие иногда полезно. Тогда тривиально, да.
Однако вопрос о том, что делать, если камни могут быть одинаковыми, остаётся...

27.05.2013, 23:52	#1
22hope22 Пользователь Регистрация: 31.03.2013 Сообщений: 52	с# Помогите, пожалуйста, с задачей для курсовой Вpемя pазбpасывать камни и вpемя соpтиpовать камни… В одном уездном гоpоде есть старое забpошенное кладбище. Оно пpедставляет собой длинный унылый pяд безымянных надгpобий в виде камней pазной фоpмы. Вес всех камней pазный. Решили привести погост в порядок, отсортировав надгpобные камни по весу. Местный обычай позволяет менять два камня местами, если между ними находится ровно K дpугих камней. Исходные данные В пеpвой стpоке находится целое число N, количество камней (1 ≤ N ≤ 130000). Каждая из следующих N стpок содеpжит целое число X, вес очеpедного камня в гpаммах (1 ≤ X ≤ 130000). Результат Должен содеpжать единственное целое число — максимальное значение K (0 ≤ K < N), которое обеспечивает возможность произвести сортировку камней по весу. Пример исходные данные 5 30 21 56 40 17 результат 1

28.05.2013, 15:29	#5
Rififi Старожил Регистрация: 19.08.2009 Сообщений: 2,119	22hope22 Помогите, пожалуйста, с задачей для курсовой в чем помочь, не вижу ни одного заданного вопроса, просто вываленное задание и всё. А вы почему со мной не соглашаетесь, у вас что, импотенция? (c) ACE Valery

28.05.2013, 16:19	#7
BDA МегаМодератор СуперМодератор Регистрация: 09.11.2010 Сообщений: 7,430	Мысли вслух: Считать данные в массив Отсортировать по возрастанию Бинарным поиском по второму массиву искать все элементы из первого массива (их новую позицию) Искать наибольший общий делитель между всеми разницами (новой и старой) в позициях (кроме 0, т.е. камень остался на месте) Средняя сложность: NlogN + NlogN/log2 + (N-1)(сложность поиска НОД) Насколько верны рассуждения не знаю. Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись ) Последний раз редактировалось BDA; 28.05.2013 в 16:23.*

28.05.2013, 00:21	#2
eval Подтвердите свой е-майл Регистрация: 29.08.2012 Сообщений: 4,011	вы сюда решили весь сборник переписать?

28.05.2013, 15:20	#3
22hope22 Пользователь Регистрация: 31.03.2013 Сообщений: 52	Ха ха ха. Прям юморист

28.05.2013, 15:24	#4
eval Подтвердите свой е-майл Регистрация: 29.08.2012 Сообщений: 4,011	какое слово рассмешило?

28.05.2013, 15:54	#6
Abstraction Старожил Регистрация: 25.10.2011 Сообщений: 3,178	Кстати, интересная задачка. Я даже за O(N^2) сходу не вижу решения.

28.05.2013, 16:40	#10
Abstraction Старожил Регистрация: 25.10.2011 Сообщений: 3,178	А. Оказывается, читать условие иногда полезно. Тогда тривиально, да. Однако вопрос о том, что делать, если камни могут быть одинаковыми, остаётся...