0 / 0 / 0
Регистрация: 04.10.2014
Сообщений: 22
1

Дефрагментация памяти

26.03.2016, 10:49. Показов 1211. Ответов 0
Метки нет (Все метки)

Память компьютера состоит из n ячеек, которые выстроены в ряд. Пронумеруем ячейки от 1 до n слева направо. Про каждую ячейку известно, свободна она или принадлежит какому-либо процессу (в таком случае известен процесс, которому она принадлежит).

Для каждого процесса известно, что принадлежащие ему ячейки занимают в памяти непрерывный участок. С помощью операций вида «переписать данные из занятой ячейки в свободную, а занятую теперь считать свободной» требуется расположить все принадлежащие процессам ячейки в начале памяти компьютера. Другими словами, любая свободная ячейка должна располагаться правее (иметь больший номер) любой занятой.

Вам необходимо найти минимальное количество операций переписывания данных из одной ячейки в другую, с помощью которых можно достичь описанных условий. Допустимо, что относительный порядок ячеек в памяти для каждого из процессов изменится после дефрагментации, но относительный порядок самих процессов должен остаться без изменений. Это значит, что если все ячейки, принадлежащие процессу i, находились в памяти раньше всех ячеек процесса j, то и после перемещений это условие должно выполняться.

Считайте, что номера всех процессов уникальны, хотя бы одна ячейка памяти занята каким-либо процессом.

Входные данные
В первой строке входных данных записано число n (1 ≤ n ≤ 200 000) — количество ячеек в памяти компьютера.

Во второй строке входных данных следуют n целых чисел a1, a2, ..., an (1 ≤ ai ≤ n), где ai равно либо 0 (это означает, что i-я ячейка памяти свободна), либо номеру процесса, которому принадлежит i-я ячейка памяти. Гарантируется, что хотя бы одно значение ai не равно 0.

Процессы пронумерованы целыми числами от 1 до n в произвольном порядке. При этом процессы не обязательно пронумерованы последовательными числами.

Выходные данные
Выведите одно целое число — минимальное количество операций, которое нужно сделать для дефрагментации памяти.

Примеры
входные данные
4
0 2 2 1
выходные данные
2
входные данные
8
0 8 8 8 0 4 4 2
выходные данные
4



заранее благодарен
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.03.2016, 10:49
Ответы с готовыми решениями:

Выделить в памяти 1024 ячейки по 8 байт и вывести их адреса(МИНИ менеджер памяти))
Вот тут появилась такая интересная задача: требуется сделать программу которая управляет 1024...

Можно ли разместить переменную в нужную ячейку памяти и реально ли хранить данные, разбросанными по памяти?
Добрый день. Не могу найти информацию по двум вопросам : 1) могу ли я разместить переменную в...

Резервирование памяти/освобождение памяти для трехмерного массива
Необходимо создать трехмерный массив (A), в котором элементы вдоль направления Z выли бы выровнены...

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

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
26.03.2016, 10:49

Дефрагментация
Выдает ошибку при выводе: Необработанное исключение типа "System.ArgumentOutOfRangeException"...

Дефрагментация
Добрый день, скажите не затронет ли дефрагментация логического диска С (системный) системные и...

Дефрагментация
Всем здрасте! Столкнулся с проблемой, не могу дефрагментировать диск С. Комп выдаёт ошибку....

Дефрагментация
В один прекрасный момент я хотел сделать фрагментацию дисков и заметил, то что на одном диске...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru