Eralim, being the mafia boss, manages a group of π fighters. Fighter π has a rating ofβ¦
- User
Eralim, being the mafia boss, manages a group of π fighters. Fighter π has a rating of ππ.
Eralim arranges a tournament of πβ1 battles, in each of which two not yet eliminated fighters π and π (1β€π<πβ€π) are chosen, and as a result of the battle, fighter π is eliminated from the tournament, and the rating of fighter π is reduced by the rating of fighter π. That is, ππ is decreased by ππ. Note that fighter π's rating can become negative. The fighters indexes do not change.
Eralim wants to know what maximum rating the last remaining fighter can preserve if he chooses the battles optimally.
Input Each test contains multiple test cases. The first line contains the number of test cases π‘ (1β€π‘β€104). The description of the test cases follows.
The first line of each test case contains a single integer π (2β€πβ€2β 105) β the number of fighters.
The second line of each test case contains π integers π1,π2,β¦ππ (1β€ππβ€109) β the ratings of the fighters.
The sum of π over all testcases does not exceed 2β 105.
Output For each testcase, output a single integer β the maximum rating that the last remaining fighter can preserve.
Example inputCopy 5 2 2 1 3 2 2 8 4 1 2 4 3 5 1 2 3 4 5 5 3 2 4 5 4 outputCopy -1 8 2 7 8 Note In the first example, you can arrange a fight between fighters with indices 1 and 2, where the fighter with index 2 will win. The rating of the last fighter, that is, the fighter with index 2, will be 1β2=β1.
In the second example, you can first conduct a fight between fighters with indices 1 and 2, where the fighter with index 2 will win, and then conduct a fight between fighters with indices 2 and 3, where the fighter with index 3 will win.
The rating of the fighter with index 2 after the first fight will be 2β2=0. The rating of the fighter with index 3 after the second fight will be 8β0=8.
- Assistant
To solve the problem of maximizing the rating of the last remaining fighter in the tournament, we can observe the following:
When choosing fighter ( k ) to be the last remaining fighter, the key is to minimize the sum subtracted from ( a_k ) during the eliminations. The optimal strategy ensures that as few fighters as possible directly subtract from ( a_k ).
Here's the main insight:
- The total sum of all fighters' ratings is ( S = \sum_{i=1}^{n} a_i ).
- To maximize the rating of the last remaining fighter ( k ), we ideally want to minimize the total rating deducted from ( a_k ). This can be achieved by arranging fights such that the second last fighter ( a_{n-1} ) subtracts as little as possible from the last fighter's rating.
- The optimal final rating of the last fighter is thus ( S - 2 \times a_{n-1} ).
This approach helps in preserving the maximum possible rating for the last fighter by strategically minimizing deductions from the second last fighter.
Example Walkthrough:
Consider the test case with fighters' ratings
[1, 2, 4, 3]:- Total sum ( S = 1 + 2 + 4 + 3 = 10 ).
- The second last fighter has a rating of ( a_{n-1} = 4 ).
- The final rating of the last fighter is ( 10 - 2 \times 4 = 2 ).
This aligns with the sample output provided.
Implementation:
The solution can be implemented in Python as follows:
def solve(): import sys input = sys.stdin.read data = input().split() idx=0 t=int(data[idx]);idx+=1 for _ in range(t): n=int(data[idx]);idx+=1 a = list(map(int, data[idx:idx+n]));idx+=n S = sum(a) if n ==1: print(a[0]) continue if n >=2: # Second last fighter is a[n-2] second_last = a[n-2] result = S - 2 * second_last print(result)