Hard Game (Çözgüdiň düşündirişi)

Solution

It's easy to show that there exists an optimal playing strategy for this game :

1. It's optimal to play all positive rounds in a row.

2. It's optimal to use largest negative score and skip largest two games and so on..

The construction will contain all positive scores that's a_i \ge 0 will be on the prefix , After that we'll consider an optimal distribution for negatives , let the list of negatives be b_m , we sort it in non decreasing order , then we consider the following pattern :

This can be maintained by a deque by using each block of [\text{largest},\text{min},\text{second min}] to not getting annoyed by index errors and shifts we update using a deque each time.

The remaining part should be reversed to get the minimum losing point (damage) and our construction is complete.

Be ware of implementation issues when a_i \ge 0 because any permutation of $a$ works for this case , since we'll neve skip rounds.

Complexity \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()