Mutasiya#4973

Mutasiya (Həll təhlili)

Genlərin permutasiyası elə yerinə yetirilməlidir ki, eyni genlər yan-yana yerləşsin. Eyni zamanda yerinə yetirilən əməliyyatların sayını minimallaşdırmaq lazımdır.

Hər təbii ədəd $a_{i}$ a_i üçün $[s_{i}; e_{i}]$ [s_i; e_i] intervallını təyin edək, burada $s_{i}$ s_i – $a_{i}$ a_i-nin ilk dəfə rast gəlindiyi pozisiyadır və $e_{i}$ e_i – $a_{i}$ a_i-nin sonuncu dəfə rast gəlindiyi pozisiyadır.

Tutaq ki, $r es$ – kəsişməyən ən böyük mümkün interval sayıdır. Bu dəyəri "tətbiq seçimi" alqoritmi ilə tapmaq olar, bu da o deməkdir ki, qalan intervallardan hər biri seçilmişlərdən ən azı biri ilə kəsişir. Bundan sonra bu intervallara uyğun gələn genlər üzərində təsvir edilmiş prosesi icra etmək lazımdır.

Əgər $k$ – qurulmuş intervalların ümumi sayıdır. Onda məsələnin cavabı $k - r es$ k - res dəyəri olacaq.

Misal

Göstərilən misal üçün intervallar belə olacaq (pozisiyaların nömrələnməsi sıfırdan başlayır):

$1 : [0; 4]$ 1: [0; 4] üçün;
$2 : [1; 6]$ 2: [1; 6] üçün;
$3 : [3; 5]$ 3: [3; 5] üçün;
$4 : [7; 7]$ 4: [7; 7] üçün;
$5 : [8; 8]$ 5: [8; 8] üçün;

Intervalı sonuna görə çeşid edək:

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

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

Kəsişməyən maksimum interval sayı $3$ -ə bərabərdir. Məsələn, $[0; 4], [7; 7], [8; 8]$ [0; 4], [7; 7], [8; 8] intervallarını seçmək olar. Qalan intervallara uyğun gələn genlər üçün məsələnin şərtində təsvir olunan prosedur yerinə yetirilməlidir. Belə genlər $2$ və $3$ -dür. İki permutasiya, məsələn, aşağıdakı kimi həyata keçirilə bilər:

Alqoritmin həyata keçirilməsi

Tutaq ki, $M A X$ – giriş ardıcıllığında ola bilən maksimum genom sayıdır.

#define MAX 100001

Cütlər cədvəli (əvvəl, sonra) intervalları $[s_{i}; e_{i}]$ [s_i; e_i] saxlayır.

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

Giriş məlumatlarını oxuyuruq. $s_{i} = - 1, e_{i} = - 1$ s_i = -1, e_i = -1 ilə başladırıq.

scanf("%d", &n);
memset(s, -1, sizeof(s));
memset(e, -1, sizeof(e));

for (i = 0; i < n; i++)
{
  scanf("%d", &x);

C++

Əgər $x$ sayı ilk dəfə rast gəlinirsə, onun pozisiyasını giriş ardıcıllığında $s_{x}$ s_x-da qeyd edirik.

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

Əgər $x$ sayı ilk dəfə rast gəlinmirsə, onun pozisiyasını $e_{x}$ e_x-da qeyd edirik, yəni $x$ -ın sonuncu rast gəlinmə pozisiyası.

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

Bütün qurulan intervalları cütlər cədvəlində $v$ -da saxlayırıq.

for (i = 1; i <= n; i++) // sayılar 1..n
  if (s[i] != -1) v.push_back(make_pair(e[i], s[i]));

İntervalar cədvələ tərsinə daxil edilir (şəkli $[e_{i}; s_{i}]$ [e_i; s_i] kimi), belə ki, cədvəlin standart çeşidlənməsi sonlarına görə artma qaydasında olur.

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

Maksimum $r es$ kəsişməyən interval sayını tapırıq.

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

$i$ -ci intervalı kəsişməzlər çoxluğuna daxil edirik. $t e m p$ dəyişən bu intervalın sonunu saxlayır (onu cari interval adlandıraq).

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

Növbəti intervalın başlanğıcı cari intervalın sonunda az olduğu halda, bu intervalı keçirik, çünki o, cari ilə kəsişir.

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

Cavabı çap edirik.

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