Çətin Oyun (Həll təhlili)

Həll

Bu oyunda optimal oynama strategiyasının mövcud olduğunu göstərmək asandır:

1. Bütün müsbət raundları ardıcıl oynamaq optimaldır.

2. Ən böyük mənfi xalı istifadə etmək və ən böyük iki oyunu atlamaq optimaldır.

Konstruksiyada bütün müsbət xallar a_i \ge 0 prefiksdə olacaq. Bundan sonra mənfi xallar üçün optimal paylanmanı nəzərdən keçirəcəyik, mənfi xalların siyahısını b_m adlandıraq, onu artan sıraya düzəldirik, sonra aşağıdakı naxışa baxırıq:

Bu, hər blok [\text{ən böyük},\text{minimum},\text{ikinci minimum}] istifadə edərək indeks xətaları və dəyişikliklərdən narahat olmamaq üçün bir deque ilə saxlanıla bilər.

Qalan hissə minimum itki xalı (zərər) əldə etmək üçün tərsinə çevrilməlidir və bizim konstruksiyamız tamamdır.

a_i \ge 0 olduqda tətbiq məsələlərinə diqqət yetirin, çünki bu halda $a$-nın istənilən permutasiya işləyir, çünki biz raundları atlamayacağıq.

Komplekslik \mathcal{O}(n \log n).

def solve():
    n=int(input())
    a=list(map(int,input().split()))
    neg=[]
    pos=[]
    for i in a:
        if i<0: neg.append(i)
        else: pos.append(i)
    if not neg:
        print(*a)
        return
    construct=[]
    neg.sort()
    for i in pos:
       construct.append(i)
    triples=len(neg)//3
    l=0
    r=len(neg)-1
    for _ in range(triples):
        construct.append(neg[r])
        r-=1
        construct.append(neg[l])
        l+=1
        construct.append(neg[l]) 
        l+=1
    rem=neg[l:r+1]
    rem.reverse()
    for i in rem: 
       construct.append(i)
    print(*construct)

t=int(input())
for _ in range(t):
    solve()