Reading Books

Editorial no oficial (C++) 

Explicación

Sea $\texttt{sum}$ igual a $\sum\limits_{i=1}^n t_i$.

Ordenamos el arreglo en orden ascendente. Kotivalo puede leer los libros en el orden $t_n, t_1, t_2, ..., t_{n-1}$, y Justiina puede leerlos en el orden $t_1, t_2, t_3, ..., t_n$.

Si $\texttt{sum} - t_n < t_n$, Justiina terminaría de leer los libros $t_1, t_2, t_3, ..., t_{n-1}$ y tendría que esperar a que Kotivalo termine de leer $t_n$. Después, Justiina puede leer $t_n$ y Kotivalo puede leer $t_1, t_2, t_3, ..., t_{n-1}$. En total, esto tomará $2 \times t_n$ unidades de tiempo.

Si $\texttt{sum} - t_n \ge t_n$, Kotivalo terminaría de leer $t_n$ antes de que Justiina termine de leer $t_1, t_2, t_3, ..., t_{n-1}$, así que Justiina no tendría que esperar a que Kotivalo termine de leer $t_n$. Así, esto tomará $\texttt{sum}$ unidades de tiempo.

Por lo tanto, la respuesta es $\max(\texttt{sum}, 2 \times t_n)$.

Implementación

Complejidad temporal: $\mathcal O(N)$.

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
int main() {
	ll n;
	cin >> n;
 
	vector<ll> books(n);
	for (ll i = 0; i < n; i++) { cin >> books[i]; }
 
	ll longest_time = *max_element(books.begin(), books.end());
	ll total_time = accumulate(books.begin(), books.end(), 0ll);
 
	cout << max(total_time, longest_time * 2) << "\n";
}

import java.io.*;
import java.util.*;
 
class ReadBook {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int n = io.nextInt();
 
		long books[] = new long[n];
		for (int i = 0; i < n; i++) { books[i] = io.nextLong(); }
 
		long longest_time = Arrays.stream(books).max().getAsLong();
		long total_time = Arrays.stream(books).sum();
 
		io.println(Math.max(total_time, longest_time * 2));
 
		io.close();
	}
 
	// CodeSnip{Kattio}
}

n = int(input())
books = [int(b) for b in input().split()]
 
longest_time = max(books)
total_time = sum(books)
 
print(max(total_time, longest_time * 2))