All-in-one Gun

Let $S=\sum_{i=1}^{n} a_i$. A full magazine always deals $S$ damage, no matter how we swap bullets, because swapping changes order, not total damage.

Now suppose the killing shot is the $r$-th bullet of some magazine, where $1 \le r \le n$. Before that magazine, we have already fired $q$ complete magazines. The total damage is

$qS + P_r,$

where $P_r$ is the damage in the first $r$ bullets of the swapped magazine. The time is

$q(n+k)+r,$

because each completed magazine costs $n$ shooting seconds plus $k$ reload seconds, and then we shoot $r$ bullets in the final magazine.

So the whole problem becomes: for every $r$, what is the maximum possible prefix sum of length $r$ after at most one swap?

Let

$\text{pref}[r]=\sum_{i=1}^{r} a_i.$

For a fixed prefix length $r$, a useful swap must move some bullet from outside the prefix into the prefix. Swapping two bullets both inside the prefix changes nothing about the prefix sum. Swapping two bullets both outside changes nothing. Swapping a prefix bullet with a suffix bullet changes the prefix sum by

$a_j-a_i,$

where $i\le r$ and $j>r$.

To maximize this gain, remove the smallest bullet currently inside the prefix and bring in the largest bullet outside the prefix. Therefore

$\text{best}[r] = \text{pref}[r] + \max(0, \text{sufMax}[r+1]-\text{prefMin}[r]),$

where $\text{prefMin}[r]=\min(a_1,\dots,a_r)$ and $\text{sufMax}[r+1]=\max(a_{r+1},\dots,a_n)$.

For $r=n$, there is no outside bullet, so no swap can improve the full-magazine prefix. In that case $\text{best}[n]=S$.

Once we know $\text{best}[r]$, the least number of complete magazines needed before the final prefix is:

0, & \text{if } \text{best}[r]\ge h,\\ \left\lceil\dfrac{h-\text{best}[r]}{S}\right\rceil, & \text{otherwise.} \end{cases}$$ Then this candidate answer is $$q(n+k)+r.$$ We take the minimum over all $r$. Why this is enough: every valid fight ends at some prefix length $r$ of a magazine after some number $q$ of complete magazines. Since the complete magazines always contribute exactly $qS$, only the final prefix can be optimized. For that final prefix, the best single swap is exactly replacing its minimum element with the maximum element outside it if profitable. There is no secret extra move hiding under the couch. Edge cases: - If the enemy dies in the first magazine, the formula naturally gives $q=0$. - If $r=n$, the final prefix is the whole magazine, so swapping is irrelevant. - Very large health needs 64-bit integers: time and damage can go far beyond `int`. Complexity is $O(n)$ per test case, with $O(n)$ memory. Since the sum of $n$ over all tests is at most $2\cdot 10^5$, this easily fits.