MEX#5880

MEX (Həll təhlili)

Varsayalım ki, $c n t$ — uzunluğu $1 0^{5}$ 10^5 olan bir tam sayı massividir. Hər bir repressiya olunmuş siyahıda olan $x$ qiyməti üçün $c n t [x] = 1$ cnt[x] = 1 olaraq təyin edəcəyik.

Sonra, $c n t [i] = 0$ cnt[i] = 0 olan ən kiçik indeksi $i$ tapmalıyıq. Giriş məlumatlarında olmayan ən kiçik sayı məhz budur. Məhz $i$ sağ qalmış hərbçilərin arasında ən istedadlı olanın nömrəsi olacaq.

Nümunə

Giriş testindəki bütün məlumatlar işlənildikdən sonra $c n t$ massivinin vəziyyətini nəzərdən keçirək.

Giriş massivində olmayan ən kiçik sayı $5$ olacaq, çünki $c n t [5] = 0$ cnt[5] = 0.

Alqoritmin reallaşdırılması

Giriş məlumatlarında olan nömrələrə sayma üçün massiv elan edəcəyik.

#define MAX 100001
int cnt[MAX];

Giriş məlumatlarını oxuyuruq. Repressiya olunmuş siyahıdaki hər bir $x$ qiyməti üçün $c n t [x] = 1$ cnt[x] = 1 təyin edirik.

scanf("%d", &n);
for (i = 0; i < n; i++)
{
  scanf("%d", &x);
  cnt[x] = 1;
}

Sonra giriş siyahısında olmayan ən kiçik qeyri-mənfi tam ədədi axtarırıq. Bunun üçün $c n t [i] = 0$ cnt[i] = 0 olan ən kiçik $i (i \geq 0)$ i~(i \ge 0) tapılmalıdır.

for (i = 0; i < MAX; i++)
  if (cnt[i] == 0)
  {
    printf("%d\n", i);
    break;
  }

Alqoritmin reallaşdırılması – bitset

Konstant $M A X$ və bit massiv $m$ elan edəcəyik.

#define MAX 100001
bitset<MAX> m;

Giriş məlumatlarını oxuyuruq. Repressiya olunmuş siyahıdaki hər bir $x$ qiyməti üçün $m [x] = t r u e$ m[x] = true təyin edirik.

scanf("%d", &n);
for (i = 0; i < n; i++)
{
  scanf("%d", &x);
  m[x] = true;
}

Sonra giriş siyahısında olmayan ən kiçik qeyri-mənfi tam ədədi axtarırıq. Bunun üçün $m [i] = 0$ m[i] = 0 olan ən kiçik $i (i \geq 0)$ i~(i \ge 0) tapılmalıdır.

for (i = 0; i < MAX; i++)
  if (!m[i])
  {
    printf("%d\n", i);
    return 0;
  }