Problema: Cruce del Río

Límite de tiempo: 1 Segundo, Límite de memoria: 128 MB Envíos: 10 Resueltos: 1 [Enviar][Estado][Foro de Discusión]Descripción del Problema

Un grupo de personas se enceuntra en la orilla derecha de un río y desea cruzar a la izquierda utilizando una única pasarela. En plena oscuridad, para cruzar necesitan luz, pero solo tienen una lámpara. Además, la pasarela permite que máximo dos personas crucen simultáneamente, ya que sería inseguro con más peso. Cada persona tarda cierto tiempo en cruzar sola, y cuando dos personas lo hacen juntas, el tiempo necesario será igual al del más lento de los dos. Se pide calcular el tiempo mínimo total requerido para que todas las personas crucen al otro lado.

Por ejemplo, si hay tres personas (A, B, C) con tiempos de cruce respectivos de 1, 2 y 4 unidades de tiempo, el tiempo mínimo total es 7. Esto se logra enviando primero a A y B, luego regresando a A con la lámpara, después cruzando a A y C, resultando en un tiempo total de 2 + 1 + 4 = 7.

Entrada

La primera línea contiene T, el número de casos de prueba. Para cada caso, la primera línea tiene N (2 ≤ N ≤ 1000), indicando cuántas personas hay. La siguiente línea contiene N números enteros separados por espacios, representando los tiempos individuales de cruce.

Salida

Para cada caso de prueba, imprima una línea con el tiempo mínimo total requerido para que todas las personas crucen.

Ejemplo de Entrada

1
4
1 2 5 10

Ejemplo de Salida

17

Análisis:

Si N == 1 o N == 2, todas las personas pueden cruzar directamente. Si N == 3, la estrategia óptima es enviar primero a las dos personas más rápidas, luego regresar con la lámpara la más rápida, y finalmente cruzar con la tercera persona. Si N ≥ 4, supongamos que t[0] representa al más rápido, t[1] al segundo más rápido, t[N-1] al más lento y t[N-2] al penúltimo más lento. Entonces:

Cuando 2t[1] + t[0] + t[N-1] > 2t[0] + t[N-1] + t[N-2], enviamos primero al más rápido junto con el más lento, luego regresa el más rápido, después cruza con el penúltimo más lento, y nuevamente regresa el más rápido.

En otro caso, enviamos primero a los dos más rápidos, luego regresa el más rápido, después cruzan los dos más lentos, y regresa el segundo más rápido.

Esto reduce el problema a N-2 personas. Repetimos hasta que queden menos de cuatro personas.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main(){
 5     int casos;
 6     cin >> casos;
 7     while(casos--){
 8         int num_personas;
 9         cin >> num_personas;
10         vector<int> tiempos(num_personas);
11         for(int i = 0; i < num_personas; ++i){
12             cin >> tiempos[i];
13         }
14         sort(tiempos.begin(), tiempos.end());
15         long long total = 0;
16         while(num_personas >= 4){
17             if(2*tiempos[1] + tiempos[0] + tiempos[num_personas-1] > 2*tiempos[0] + tiempos[num_personas-1] + tiempos[num_personas-2]){
18                 total += tiempos[num_personas-1] + tiempos[0] + tiempos[num_personas-2] + tiempos[0];
19             }
20             else{
21                 total += tiempos[1] + tiempos[0] + tiempos[num_personas-1] + tiempos[1];
22             }
23             num_personas -= 2;
24         }
25         if(num_personas == 3){
26             total += tiempos[2] + tiempos[0] + tiempos[1];
27         }
28         else if(num_personas == 2){
29             total += tiempos[1];
30         }
31         else if(num_personas == 1){
32             total += tiempos[0];
33         }
34         cout << total << endl;
35     }
36     return 0;
37 }