Екзамен в Нічну Варту (Розбір)

Ідея

Переформулюємо визначення функції $f(p)$. $f(p)$ — кількість таких індексів 1 \le i \le n-2, для яких виконується умова p_i \not\equiv p_{i+1} \pmod{2}.Очевидно,що f(p)\le n-2.При цьому існує всього чотири розташування парних та непарних чисел, які дають результат f(p) = n-2.

1. 1,0,0,1,1,0,0,1...

2. 1,1,0,0,1,1,0,0...

3. 0,1,1,0,0,1,1,0...

4. 0,0,1,1,0,0,1,1...

0 — парні числа, 1 — непарні. Так як ми хочемо, щоб перестановка була лексикографічно мінімальною, ми будемо ставити найменше число відповідної парності.Тоді нескладно помітити,що серед всіх розташувань перше буде давати лексикографічно мінімальну перестановку. Але є один нюанс. Коли n \equiv 3 \pmod{4}, нам знадобиться \lceil \frac{n}{2} \rceil парних чисел та \lfloor \frac{n}{2} \rfloor — непарних, в той час як у нас є \lfloor \frac{n}{2} \rfloor — парних та \lceil \frac{n}{2} \rceil — непарних. В такому випадку слід будувати перестановку за другим патерном,тобто 1,1,0,0,1.... Будемо підтримувати дві змінні first_odd — найменше непарне число, яке ще не зустрічалось в перестановці, і аналогічно first_even — найменше парне. Попередньо оберемо патерн, за яким будемо будувати перестановку, та будемо йти по числам 3 \le i \le n і вибирати, яке з чисел ставити, та збільшувати відповідне число на два.

Отже, загальна асимптотика — $O(n)$.

#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  vector<int> ans(n);
  int first_odd = 1, first_even = 2;
  if (n % 4 == 3) {
    ans[0] = 1;
    ans[1] = 3;
    first_odd = 5;
  } else {
    ans[0] = 1;
    ans[1] = 2;
    first_odd = 3, first_even = 4;
  }
  for (int i = 2; i < n; i++)
    if (ans[i - 2] & 1) ans[i] = first_even, first_even += 2;
    else ans[i] = first_odd, first_odd += 2;
  for (int i = 0; i < n; i++) cout << ans[i] << (i == n - 1 ? '\n' : ' ');
}