PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Abhinav Sharma
Testers: Nishank Suresh, Nishant Shah
Editorialist: Nishank Suresh
DIFFICULTY:
1230
PREREQUISITES:
None
PROBLEM:
There are two trains A and B, and N stations. A train takes time P_i to go from station i to station (i+1).
Train B can depart from station i only after train A has reached station (i+1). What is the minimum amount of time needed for train B to reach station N?
EXPLANATION:
Let S = P_1 + P_2 + \ldots + P_{N-1}, i.e, the sum of all the elements of P.
Let M = \max(P_1, P_2, \ldots, P_{N-1}), i.e, the maximum element of P.
Then the answer is just S + M.
How?
The journey of train B can be broken into two separate parts: time taken by it when travelling from one station to another, and time taken while waiting for train A to reach the next station.
The time taken while travelling is clearly just P_1 + P_2 + \ldots + P_{N-1}, by definition.
Now, let M = \max(P_1, P_2, \ldots, P_{N-1}).
The minimum waiting time is definitely at least M, since while train A crosses the section that needs M time, train B cannot move along that section at all, and hence must wait for a total of \geq M units of time already.
Conversely, suppose train B just waits for M seconds at the very beginning before even starting, and starts moving at the end of the M-th second. It is easy to see that, since M = \max(P_1, P_2, \ldots, P_{N-1}), whenever train B is at station i, train A has already reached station (i+1) (and may have gone even further). So, no more waiting time is needed.
Thus, the minimum waiting time is exactly M, and hence the answer is S + M as claimed.
TIME COMPLEXITY
\mathcal{O}(N) per test case
CODE:
Editorialist's Code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
print(sum(a) + max(a))