4973. Мутация

Ученые-генетики планеты Олимпия опять проводят эксперименты с ДНК примитивных организмов. Геном организма – это последовательность генов, каждый из которых можно закодировать одним натуральным числом. Гены, которые кодируются одними и теми же числами, считаются одинаковыми, и наоборот, гены, которые кодируются разными числами, считаются разными.

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

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

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

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

Вход. Первая строка содержит количество генов n (1 ≤ n ≤ 10⁵) в геноме примитивного организма. В следующей строке записано n натуральных чисел, каждое из которых не превышает n – последовательность генов в геноме.

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

Пример входа	Пример выхода
9 1 2 1 3 1 3 2 4 5	2

РЕШЕНИЕ

жадность

Анализ алгоритма

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

Каждому натуральному числу a_i поставим в соответствие отрезок [s_i; e_i], где s_i – позиция, в которой a_i встречается впервые, а e_i – позиция, в которой a_i встречается в последний раз.

Пусть res – наибольшее возможное количество непересекающихся отрезков. Это значение находим с помощью алгоритма “выбора заявок”. Это означает, что каждый из остальных отрезков пересекается хотя бы с одним из выбранных. И над генами, им отвечающим, необходимо провести описанную процедуру.

Если k – число всех построенных отрезков, то ответом на задачу будет значение k – res.

Пример

Для приведенного примера отрезки будут иметь вид (нумеровать позиции будем с нуля):

· для 1: [0; 4];

· для 2: [1; 6];

· для 3: [3; 5];

· для 4: [7; 7];

· для 5: [8; 8];

Отсортируем отрезки по координате конца:

[0; 4], [3; 5], [1; 6], [7; 7], [8; 8]

Максимальное количество непересекающихся отрезков равно 3. Например, можно выбрать отрезки [0; 4], [7; 7], [8; 8]. Над генами, отвечающим остальным отрезкам, следует проводить описанную в условии задачи процедуру. Таковыми генами являются 2 и 3. Две перестановки можно, например, произвести следующим образом:

Реализация алгоритма

Пусть MAX – максимальное возможное количество геномов во входной последовательности.

#define MAX 100001

Вектор пар v хранит отрезки [s_i; e_i].

vector<pair<int, int> > v;

int s[MAX], e[MAX];

Читаем входные данные. Инициализируем s[i] = -1, e[i] = -1.

scanf("%d", &n);

memset(s, -1, sizeof(s));

memset(e, -1, sizeof(e));

for (i = 0; i < n; i++)

{

scanf("%d", &x);

Если число x встречается впервые, то его позицию во входной последовательности заносим в s[x].

if (s[x] == -1) s[x] = i;

Если число x встречается не первый раз, то его позицию заносим в e[x], считая что x встречается в последний раз.

if (i > e[x]) e[x] = i;

}

Все построенные отрезки заносим в вектор v.

for (i = 1; i <= n; i++) // numbers 1..n

if (s[i] != -1) v.push_back(make_pair(e[i], s[i]));

Отрезки заносили в вектор задом наперед (в виде [e_i; s_i]), чтобы по умолчанию сортировка отрезков происходила в возрастающем порядке их концов.

sort(v.begin(), v.end());

Находим максимальное количество res непересекающихся отрезков.

i = res = 0;

while (i < v.size())

{

i-ый отрезок добавляем во множество непересекающихся отрезков. Переменная temp содержит конец этого отрезка (назовем его текущим отрезком).

res++; temp = v[i++].first; // end

Пока начало следующего отрезка меньше конца текущего, такой отрезок пропускаем (он пересекается с текущим).

while (i < v.size() && v[i].second < temp) i++;

}

Выводим ответ.

printf("%d\n", v.size() - res);