Gecə Növbətçiləri üçün imtahan (Həll təhlili)

İdeya

Gəlin $f(p)$ funksiyasının tərifini yenidən formalaşdıraq. $f(p)$ — 1 \le i \le n-2 olan və p_i \not\equiv p_{i+1} \pmod{2} şərtinin ödənildiyi indekslərin sayıdır. Aydındır ki, f(p)\le n-2. Eyni zamanda, f(p) = n-2 nəticəsini verən cüt və tək ədədlərin yalnız dörd düzülüşü var.

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 — cüt ədədlər, 1 — tək ədədlər. Permutasiyanın leksikoqrafik cəhətdən ən kiçik olmasını istədiyimiz üçün, uyğun paritetə malik ən kiçik ədədi yerləşdirəcəyik. Onda asanlıqla görmək olar ki, bütün düzülüşlər arasında birinci düzülüş leksikoqrafik cəhətdən ən kiçik permutasiyanı verəcək. Amma bir nüans var. n \equiv 3 \pmod{4} olduqda, bizə \lceil \frac{n}{2} \rceil cüt ədəd və \lfloor \frac{n}{2} \rfloor — tək ədəd lazım olacaq, halbuki bizdə \lfloor \frac{n}{2} \rfloor — cüt ədəd və \lceil \frac{n}{2} \rceil — tək ədəd var. Bu halda permutasiyanı ikinci şablona uyğun qurmalıyıq, yəni 1,1,0,0,1.... Biz iki dəyişəni saxlayacağıq: first_odd — permutasiyada hələ görünməmiş ən kiçik tək ədəd, və oxşar şəkildə first_even — ən kiçik cüt ədəd. Əvvəlcə permutasiyanı hansı şablona görə quracağımızı seçirik, sonra isə 3 \le i \le n ədədləri üzrə keçərək hansı ədədi yerləşdirəcəyimizi müəyyən edirik və uyğun ədədi iki vahid artırırıq.

Beləliklə, ümumi mürəkkəblik $O(n)$-dir.

#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' : ' ');
}