Мутація#4973

Мутація (Розбір)

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

Кожному натуральному числу $a_{i}$ a_i поставимо у відповідність відрізок $[s_{i}; e_{i}]$ [s_i; e_i], де $s_{i}$ s_i — позиція, на якій $a_{i}$ a_i зустрічається вперше, а $e_{i}$ e_i — позиція, на якій $a_{i}$ a_i зустрічається в останній раз.

Нехай $r es$ — найбільше можливе число непересічних відрізків. Це значення можна знайти за допомогою алгоритму "вибору заявок", що означає, що кожен із залишених відрізків перетинається хоча б з одним із обраних. Після цього потрібно виконати описану процедуру над генами, яким ці відрізки відповідають.

Якщо $k$ — загальна кількість побудованих відрізків. Тоді відповіддю на задачу буде значення $k - r es$ k - res.

Приклад

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

для $1 : [0; 4]$ 1: [0; 4];
для $2 : [1; 6]$ 2: [1; 6];
для $3 : [3; 5]$ 3: [3; 5];
для $4 : [7; 7]$ 4: [7; 7];
для $5 : [8; 8]$ 5: [8; 8];

Відсортуємо відрізки по координаті кінця:

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

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

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

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

Нехай $M A X$ — максимальна можлива кількість геномів у вхідній послідовності.

#define MAX 100001

Вектор пар $v$ зберігає відрізки $[s_{i}; e_{i}]$ [s_i; e_i].

vector<pair<int, int> > v;
int s[MAX], e[MAX];

Читаємо вхідні дані. Ініціалізуємо $s_{i} = - 1, e_{i} = - 1$ 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);

C++

Якщо число $x$ зустрічається вперше, то його позицію у вхідній послідовності записуємо в $s_{x}$ s_x.

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

Якщо число $x$ зустрічається не вперше, то його позицію записуємо в $e_{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}]$ [e_i; s_i]), щоб за замовчуванням сортування відрізків відбувалося в порядку зростання їх кінців.

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

Знаходимо максимальну кількість $r es$ непересічних відрізків.

i = res = 0;
while (i < v.size())
{

Додаємо $i$ -й відрізок у множину непересічних відрізків. Змінна $t e m p$ містить кінець цього відрізка (назвемо його поточним відрізком).

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

Поки початок наступного відрізка менше кінця поточного, пропускаємо такий відрізок, так як він перетинається з поточним.

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

Виводимо відповідь.

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