codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.