Skip to Content
CTRL K

Lemonade Line

Pista 1

Consideremos cómo se pueden procesar las vacas para minimizar el número de vacas que se unen a la fila. Pensemos en las situaciones posibles en las que una vaca estaría dispuesta a esperar detrás de las demás.

Pista 2

Este problema se resuelve mejor con un enfoque voraz. Consideremos qué estructuras de datos serán útiles para obtener a la vaca más dispuesta a esperar en la fila.

Solución

Análisis oficial (C++) 

La estrategia voraz es poner a las vacas con menor tiempo de espera al final de la fila.

Implementación

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

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
int main() {
	freopen("lemonade.in", "r", stdin);
	freopen("lemonade.out", "w", stdout);
 
	int n;
	cin >> n;
 
	vector<int> cows(n);
	for (int i = 0; i < n; i++) { cin >> cows[i]; }
 
	int ans = 0;
	sort(cows.begin(), cows.end(), greater<int>());
 
	for (int i = 0; i < n; i++) {
		if (i <= cows[i]) {
			ans++;
		} else {
			break;
		}
	}
	cout << ans << "\n";
}
import java.io.*;
import java.util.*;
class cows {
	int vals;
	public cows(int vals) { this.vals = vals; }
	public int getVals() { return this.vals; }
}
class Sort implements Comparator<cows> {  // Comparador especializado en
	                                      // O(log N) para límites de tiempo simples.
	public int compare(cows a, cows b) { return Integer.compare(b.vals, a.vals); }
}
public class lemonade {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(new File("lemonade.in"));
		PrintWriter out =
		    new PrintWriter(new BufferedWriter(new FileWriter("lemonade.out")));
		int N = sc.nextInt();
		ArrayList<cows> arr = new ArrayList<>();
		int ans = 0;
		for (int i = 0; i < N; i++) { arr.add(new cows(sc.nextInt())); }
 
		while (true) {
			arr.sort(new Sort());
			int toRemove = arr.get(0).getVals();
			if (toRemove >= ans) {
				arr.remove(0);
				ans++;
			} else {
				break;
			}
		}
		out.println(ans);
		out.close();
	}
}
import sys
 
sys.stdin = open("lemonade.in", "r")
sys.stdout = open("lemonade.out", "w")
 
n = int(input())
cows = list(map(int, input().split()))
cows.sort(reverse=True)
ans = 0
 
for i in range(n):
	if i <= cows[i]:
		ans += 1
	else:
		break
 
print(ans)
Fundamentos