Складна гра (Розбір)

Рішення

Легко показати, що існує оптимальна стратегія гри для цієї гри:

1. Оптимально грати всі позитивні раунди підряд.

2. Оптимально використовувати найбільший негативний бал і пропустити найбільші два раунди і так далі..

Конструкція міститиме всі позитивні бали, тобто a_i \ge 0, які будуть на префіксі. Після цього ми розглянемо оптимальний розподіл негативів, нехай список негативів буде b_m, ми сортуємо його в невисхідному порядку, потім розглядаємо наступний шаблон:

Це можна підтримувати за допомогою деку, використовуючи кожен блок [\text{найбільший},\text{мінімальний},\text{другий мінімальний}], щоб уникнути помилок індексації та зсувів, ми оновлюємо за допомогою деку кожного разу.

Залишену частину слід перевернути, щоб отримати мінімальні втрати (пошкодження), і наша конструкція завершена.

Будьте обережні з проблемами реалізації, коли a_i \ge 0, оскільки будь-яка перестановка $a$ підходить для цього випадку, оскільки ми ніколи не пропустимо раунди.

Складність \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()