Skyline#12306

Skyline (Həll təhlili)

Problem Müəllifi:	Hasan Saleh (MathModel)
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Bizə ${1, 2, \dots, n}$ \{1,2,\dots,n\} dəstinin bir permutasiya $p$ verilir və biz

a_{i} = \frac{p _{i}}{i} .

a_i=\frac{p_i}{i}.

Tələb olunan şərt

a_{1} < a_{2} > a_{3} < a_{4} > a_{5} < \dots

a_1<a_2>a_3<a_4>a_5<\dots

yəni, cüt indekslər lokal maksimumlar, tək indekslər isə lokal minimumlardır.

Bir-birini birbaşa müqayisə etmək əvəzinə, daha güclü bir invariant tətbiq edirik:

hər cüt indeks $i$ üçün,
$a_{i} > 1,$
a_i>1,
hər tək indeks $i \geq 3$ i\ge3 üçün,
$a_{i} < 1.$
a_i<1.

Əgər bu şərtlər yerinə yetirilirsə, zig-zag şərti avtomatik olaraq təmin edilir.

Beləliklə, yalnız bu qeyri-bərabərlikləri təmin edən bir permutasiya lazımdır.

Konstruksiya

$p_{1} = 1,$
p_1=1,
beləliklə
$a_{1} = 1.$
a_1=1.
hər cüt indeks $i < n$ i<n üçün,
$p_{i} = i + 1, a_{i} = \frac{i + 1}{i} > 1.$
p_i=i+1, \qquad a_i=\frac{i+1}{i}>1.
hər tək indeks $i \geq 3$ i\ge3 üçün,
$p_{i} = i - 1, a_{i} = \frac{i - 1}{i} < 1.$
p_i=i-1, \qquad a_i=\frac{i-1}{i}<1.
əgər $n$ cütdürsə,
$p_{n} = n, a_{n} = 1.$
p_n=n, \qquad a_n=1.

Bu, birbaşa

p = [1, 3, 2, 5, 4, 7, 6, \dots]

p=[1,\,3,\,2,\,5,\,4,\,7,\,6,\,\dots]

verir (əgər $n$ cütdürsə, $n$ sonunda).

Bütün $n \geq 1$ n\ge1 üçün etibarlı bir konstruksiya mövcuddur, beləliklə, biz heç vaxt $- 1$ çıxarmırıq.

Komplekslik $O (n)$ .

for _ in range(int(input())):
    n=int(input())
    p=[0]*n
    for i in range(n):p[i]=i+1
    for i in range(1,n-1,2):
        p[i],p[i+1]=p[i+1],p[i]
    a=[p[i]/(i+1) for i in range(n)]
    for i in range(1,n-1):
        if(i%2==0):
            assert(a[i-1]>a[i] and a[i]<a[i+1])
        else:
            assert(a[i-1]<a[i] and a[i]>a[i+1])
    print(*p)

Python