Smilo and Monsters
Contest: Codeforces Round 907 (Div. 2)
Difficulty rating: 1500
Tags: binary search, constructive algorithms, greedy, sortings, two pointers

A boy called Smilo is playing a new game! In the game, there are $$$n$$$ hordes of monsters, and the $$$i$$$-th horde contains $$$a_i$$$ monsters. The goal of the game is to destroy all the monsters. To do this, you have two types of attacks and a combo counter $$$x$$$, initially set to $$$0$$$:

- The first type: you choose a number $$$i$$$ from $$$1$$$ to $$$n$$$, such that there is at least one monster left in the horde with the number $$$i$$$. Then, you kill one monster from horde number $$$i$$$, and the combo counter $$$x$$$ increases by $$$1$$$.
- The second type: you choose a number $$$i$$$ from $$$1$$$ to $$$n$$$, such that there are at least $$$x$$$ monsters left in the horde with number $$$i$$$. Then, you use an ultimate attack and kill $$$x$$$ monsters from the horde with number $$$i$$$. After that, $$$x$$$ is reset to zero.

Your task is to destroy all of the monsters, meaning that there should be no monsters left in any of the hordes. Smilo wants to win as quickly as possible, so he wants to the minimum number of attacks required to win the game.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The descriptions of the test cases follow.

The first line of each input data set contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of hordes of monsters.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the number of monsters in each horde.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot {10^5}$$$.

Output format:
For each test case, out put the minimum number of attacks required to kill all monsters.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we can use an attack of the first type on the $$$1$$$-st, $$$3$$$-rd and $$$4$$$-th hordes, and then use an attack of the second type to finish off the $$$2$$$-nd horde. We need $$$4$$$ attacks in total.

In the second test case, we can use an attack of the first type on the $$$1$$$-st and $$$3$$$-rd hordes, then use an attack of the second type to finish off the $$$2$$$-nd horde, and then use an attack of the first type on the $$$4$$$-th horde. We need $$$4$$$ attacks in total.

In the fourth test case, we can use an attack of the first type once on the $$$1$$$-st horde, twice on the $$$2$$$-nd horde, and then use an attack of the second type on the $$$2$$$-nd horde, and finally use an attack of the first type to finish off the $$$2$$$-nd horde. We need $$$5$$$ attacks in total.

Example input:
4
4
1 3 1 1
4
1 2 1 1
6
3 2 1 5 2 4
2
1 6

Example output:
4
4
11
5

Editorial:
Note that if the second operation were free, we would need $$$\lceil \frac{sum}{2} \rceil$$$ operations to get rid of all the monsters. Indeed, when we kill one monster, we can kill a second monster for free with a second operation. But the second operation is not free. So we need to use the second operation as little as possible.
To do this, we need to apply ultimates (second attack) on the current largest horde by number of monsters, when the combo counter reaches the size of the largest horde. And we apply the first attack on the smallest hordes. This is so because the combo counter allows us to defeat $$$\lceil \frac{sum}{2} \rceil$$$ monsters. But since we can't apply this operation on several hordes at once, we need to keep the number of hordes on which we apply these attacks of the second type as small as possible. Then we can use the greedy algorithm described above. Formally, we need to keep a sorted array and store two pointers: pointer $$$i$$$ — to the smallest horde, $$$j$$$ — to the largest horde. Until $$$i$$$ is equal to $$$j$$$: if after destroying all horde $$$i$$$ we can't kill horde $$$j$$$ with ultimates, we destroy horde $$$i$$$, increase pointer $$$i$$$ by $$$1$$$ and increase combo counter $$$x$$$ by $$$a$$$[$$$i$$$]. Otherwise, hit the horde $$$i$$$ so many times that the combo counter $$$x$$$ becomes $$$a$$$[$$$j$$$]. Then apply a second attack on horde $$$j$$$, reduce horde $$$j$$$'s counter by $$$1$$$, reduce $$$a$$$[$$$i$$$], and nullify the combo counter. When $$$i$$$ becomes equal to $$$j$$$, you just need to apply the first attack the right number of times to finish with ultimates (or not if $$$a$$$[$$$i$$$] $$$=$$$ $$$1$$$).
Total complexity $$$O$$$($$$nlogn$$$).