649D.md (4561B)
1 Source: https://codeforces.com/problemset/problem/649/D 2 3 D. Дефрагментация памяти 4 5 ограничение по времени на тест 6 7 2 секунды 8 9 ограничение по памяти на тест 10 11 256 мегабайт 12 13 ввод 14 15 стандартный ввод 16 17 вывод 18 19 стандартный вывод 20 21 Память компьютера состоит из *n* ячеек, которые выстроены в ряд. Пронумеруем ячейки от 1 до *n* слева направо. Про каждую ячейку известно, свободна она или принадлежит какому-либо процессу (в таком случае известен процесс, которому она принадлежит). 22 23 Для каждого процесса известно, что принадлежащие ему ячейки занимают в памяти непрерывный участок. С помощью операций вида «переписать данные из занятой ячейки в свободную, а занятую теперь считать свободной» требуется расположить все принадлежащие процессам ячейки в начале памяти компьютера. Другими словами, любая свободная ячейка должна располагаться правее (иметь больший номер) любой занятой. 24 25 Вам необходимо найти минимальное количество операций переписывания данных из одной ячейки в другую, с помощью которых можно достичь описанных условий. Допустимо, что относительный порядок ячеек в памяти для каждого из процессов изменится после дефрагментации, но относительный порядок самих процессов должен остаться без изменений. Это значит, что если все ячейки, принадлежащие процессу *i*, находились в памяти раньше всех ячеек процесса *j*, то и после перемещений это условие должно выполняться. 26 27 Считайте, что номера всех процессов уникальны, хотя бы одна ячейка памяти занята каким-либо процессом. 28 29 Входные данные 30 31 В первой строке входных данных записано число *n* (1 ≤ *n* ≤ 200 000) — количество ячеек в памяти компьютера. 32 33 Во второй строке входных данных следуют *n* целых чисел *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ *n*), где *a**i* равно либо 0 (это означает, что *i*-я ячейка памяти свободна), либо номеру процесса, которому принадлежит *i*-я ячейка памяти. Гарантируется, что хотя бы одно значение *a**i* не равно 0. 34 35 Процессы пронумерованы целыми числами от 1 до *n* в произвольном порядке. При этом процессы не обязательно пронумерованы последовательными числами. 36 37 Выходные данные 38 39 Выведите одно целое число — минимальное количество операций, которое нужно сделать для дефрагментации памяти. 40 41 Примеры 42 43 Входные данные 44 45 ``` 46 4 47 0 2 2 1 48 ``` 49 50 Выходные данные 51 52 ``` 53 2 54 ``` 55 56 Входные данные 57 58 ``` 59 8 60 0 8 8 8 0 4 4 2 61 ``` 62 63 Выходные данные 64 65 ``` 66 4 67 ``` 68 69 Примечание 70 71 В первом тестовом примере достаточно двух операций: 72 73 1. Переписать данные из третьей ячейки в первую. После этого память компьютера примет вид: 2 2 0 1. 74 2. Переписать данные из четвертой ячейки в третью. После этого память компьютера примет вид: 2 2 1 0.