Why Did the Cow Cross the Road III

Solución en video

Por Varun Ragunath

Código de la solución en video

C++Java


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	freopen("cowqueue.in", "r", stdin);
	freopen("cowqueue.out", "w", stdout);
	cin.sync_with_stdio(0);
	cin.tie(0);
 
	// leemos la entrada
	// cantidad de vacas, información de cada vaca
 
	int n;
	cin >> n;
 
	vector<pair<int, int>> cows(n);
 
	for (int i = 0; i < n; i++) { cin >> cows[i].first >> cows[i].second; }
 
	// ahora hay que determinar el orden óptimo
	// claramente ordenar es la "mejor" y única forma de ordenar las vacas
 
	// para ordenar las vacas podemos usar una implementación de librería o bubble
	// sort
 
	// acá implementamos bubble sort
 
	bool swapped = true;
 
	while (swapped) {
		swapped = false;
		for (int i = 0; i < n - 1; i++) {
			if (cows[i] > cows[i + 1]) {
				swap(cows[i], cows[i + 1]);
				swapped = true;
			}
		}
	}
 
	// ahora que ordenamos el arreglo, es momento de simular el proceso
 
	int cur_time = 0;  // guarda el tiempo actual
 
	for (int i = 0; i < n; i++) {
		// si el tiempo de la vaca actual que estamos procesando ya pasó
		// hay que actualizar su tiempo al tiempo actual
		cows[i].first = max(cows[i].first, cur_time);
		// ahora hay que calcular cuándo podrá salir del
		// interrogatorio
		cur_time = cows[i].first + cows[i].second;
		// cur_time ahora guarda el tiempo necesario para procesar las primeras i
		// vacas
	}
 
	cout << cur_time << '\n';
 
	return 0;
}


import java.io.*;
import java.util.*;
 
public class cowqueue {
	public static void main(String[] args) throws IOException {
		cowqueue.Kattio io = new cowqueue.Kattio("cowqueue");
 
		// leemos la entrada
		// cantidad de vacas, información de cada vaca
		int n = io.nextInt();
		int[][] cows = new int[n][2];
 
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 2; j++) { cows[i][j] = io.nextInt(); }
		}
 
		// hay que generar el orden óptimo de las vacas
		// claramente el orden óptimo es simplemente ordenar las vacas por
		// tiempo de llegada; podemos usar bubble sort
 
		boolean swapped = true;
 
		while (swapped) {
			swapped = false;
			for (int i = 0; i < n - 1; i++) {
				if (cows[i][0] > cows[i + 1][0]) {
					// ¿cómo se escribe un swap en java????
					int ext = cows[i][0];
					cows[i][0] = cows[i + 1][0];
					cows[i + 1][0] = ext;
 
					ext = cows[i][1];
					cows[i][1] = cows[i + 1][1];
					cows[i + 1][1] = ext;
 
					swapped = true;
				}
			}
		}
 
		// ahora es momento de simular el proceso
		int cur_time = 0;  // guarda el tiempo actual
 
		for (int i = 0; i < n; i++) {
			// actualizamos el tiempo en que cow[i] empieza el interrogatorio
			cows[i][0] = Math.max(cur_time, cows[i][0]);
			// ahora que tenemos el tiempo en que la i-ésima vaca entra a la cola,
			// calculamos cuándo sale de la cola
			cur_time = (cows[i][0] + cows[i][1]);
		}
 
		io.println(cur_time);
		io.close();
	}
 
	// CodeSnip{Kattio}
}

Explicación

Como conocemos los tiempos de llegada y los tiempos de procesamiento de todas las vacas, intuitivamente las procesamos por tiempo de llegada.

Para explicarlo, consideremos procesar una vaca que llegó más tarde antes que una que llegó más temprano. Entonces, en el momento en que procesamos a la vaca tardía, la temprana ya debe estar esperando. Como ambas están disponibles para el interrogatorio y procesar a la temprana nunca perjudica, siempre podemos interrogar a la temprana antes que a la tardía y reducir la espera.

Así, podemos ordenar las vacas por tiempo de llegada y luego procesarlas una por una. Podemos llevar registro de cuándo empieza el interrogatorio de cada vaca, ya que es el máximo entre su tiempo de llegada y el momento en que terminó el interrogatorio de la vaca anterior. Iterar por todas las vacas con esta lógica nos permite calcular la respuesta final.

Implementación

Complejidad temporal: $\mathcal{O}(N \log N)$

C++JavaPython


#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
	freopen("cowqueue.in", "r", stdin);
	int n;
	cin >> n;
 
	vector<pair<int, int>> cows(n);
	for (int i = 0; i < n; i++) { cin >> cows[i].first >> cows[i].second; }
 
	sort(cows.begin(), cows.end());
 
	int curr_time = 0;
	for (const pair<int, int> &c : cows) {
		// esta vaca ya estaba esperando, sumamos la duración al tiempo actual.
		if (curr_time > c.first) {
			curr_time += c.second;
		} else {
			// la última vaca terminó antes de que llegara esta,
			// así que el tiempo actual pasa a ser cuando esta vaca termina.
			curr_time = c.first + c.second;
		}
	}
 
	freopen("cowqueue.out", "w", stdout);
	cout << curr_time << endl;
}


import java.io.*;
import java.util.*;
 
class CowQueue {
	// BeginCodeSnip{Cow Class}
	static class Cow {
		public int arrival;
		public int duration;
 
		public Cow(int arrival, int duration) {
			this.arrival = arrival;
			this.duration = duration;
		}
	}
	// EndCodeSnip
 
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("cowqueue.in"));
		int n = Integer.parseInt(read.readLine());
 
		Cow[] cows = new Cow[n];
		for (int i = 0; i < n; i++) {
			StringTokenizer cow = new StringTokenizer(read.readLine());
			cows[i] = new Cow(Integer.parseInt(cow.nextToken()),
			                  Integer.parseInt(cow.nextToken()));
		}
		read.close();
 
		Arrays.sort(cows, Comparator.comparingInt(c -> c.arrival));
 
		int currTime = 0;
		for (Cow c : cows) {
			// esta vaca ya estaba esperando, sumamos la duración al tiempo actual
			if (currTime > c.arrival) {
				currTime += c.duration;
			} else {
				// la última vaca terminó antes de que llegara esta,
				// así que el tiempo actual pasa a ser cuando esta vaca termina.
				currTime = c.arrival + c.duration;
			}
		}
 
		PrintWriter written = new PrintWriter("cowqueue.out");
		written.println(currTime);
		written.close();
	}
}


import sys
 
sys.stdin = open("cowqueue.in")
 
n = int(input())
 
cows = []
for i in range(n):
	cows.append(list(map(int, input().split())))
 
cows.sort()
 
curr_time = 0
for c in cows:
	# esta vaca ya estaba esperando, sumamos la duración al tiempo actual.
	if curr_time > c[0]:
		curr_time += c[1]
	else:
		# la última vaca terminó antes de que llegara esta,
		# así que el tiempo actual pasa a ser cuando esta vaca termina.
		curr_time = c[0] + c[1]
 
print(curr_time, file=open("cowqueue.out", "w"))