MEX#5880

MEX (Розбір)

Припустимо, що $c n t$ — цілочисловий масив довжини $1 0^{5}$ 10^5. Для кожного значення $x$ з вхідного списку репресованих встановимо $c n t [x] = 1$ cnt[x] = 1.

Потім потрібно знайти найменший індекс $i$ , для якого $c n t [i] = 0$ cnt[i] = 0. Це число і є мінімальним з тих, які відсутні у вхідних даних. Саме $i$ буде номером найталановитішого з залишених живими військових.

Приклад

Розглянемо стан масиву $c n t$ після обробки всіх даних вхідного тесту.

Найменшим числом, відсутнім у вхідному масиві, буде $5$ , оскільки $c n t [5] = 0$ cnt[5] = 0.

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

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

#define MAX 100001
int cnt[MAX];

Читаємо вхідні дані. Для кожного значення $x$ з списку репресованих встановлюємо $c n t [x] = 1$ cnt[x] = 1.

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

Далі шукаємо найменше невід'ємне ціле число, відсутнє у вхідному списку. Для цього потрібно знайти мінімальне $i (i \geq 0)$ i~(i \ge 0), для якого $c n t [i] = 0$ cnt[i] = 0.

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

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

Оголошуємо константу $M A X$ і бітовий масив $m$ .

#define MAX 100001
bitset<MAX> m;

Читаємо вхідні дані. Для кожного значення $x$ з списку репресованих встановлюємо $m [x] = t r u e$ m[x] = true.

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

Далі шукаємо найменше невід'ємне ціле число, відсутнє у вхідному списку. Для цього потрібно знайти мінімальне $i (i \geq 0)$ i~(i \ge 0), для якого $m [i] = 0$ m[i] = 0.

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