Skip to Content
CTRL K

Bovine Acrobatics

Análisis oficial (Python) 

Explicación

Nótese que es óptimo colocar las vacas más pesadas abajo y las más livianas arriba, lo que hace el hueco lo más grande posible. Por tanto, podemos ordenar las vacas de más pesada a más liviana. Mantenemos una cola ordenada con estas vacas. Para cada vaca, si no se puede añadir a la torre del frente de nuestra cola, sabemos que no se puede añadir a ninguna torre, y por tanto esa vaca se puede ignorar.

Sin embargo, esto toma O(Nlog⁡N)\mathcal{O}(N \log N) operaciones para NN vacas en total, que es demasiado lento. Para optimizarlo, en lugar de considerar vacas de forma individual, podemos agrupar torres que tienen pesos equivalentes de vaca en la cima. Luego, manteniendo una cola de grupos de torres ordenada por peso, podemos procesar todas las vacas en O(N)\mathcal{O}(N).

Cada vez que procesamos un grupo de vacas con el mismo peso, terminaremos añadiendo un grupo nuevo de vacas a nuestra cola. Como procesamos las vacas en orden ordenado, este grupo más nuevo de torres se colocará al final de la cola, lo que mantiene el orden ordenado de la cola.

Implementación

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

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main() {
	int n, m, k;
	cin >> n >> m >> k;
	vector<array<int, 2>> cowGroups(n);
	for (int i = 0; i < n; i++) {
		cin >> cowGroups[i][0] >> cowGroups[i][1];
		cowGroups[i][1] = min(cowGroups[i][1], m);
	}
 
	// Lista ordenada de vacas
	sort(cowGroups.begin(), cowGroups.end());
	reverse(cowGroups.begin(), cowGroups.end());
 
	// Deque que guarda las torres según pares de peso y cantidad
	deque<array<ll, 2>> towers;
 
	// Valor grande para la torre original
	towers.push_back({INT_MAX, m});
 
	ll count = 0;
	for (int i = 0; i < n; i++) {
		ll amt = cowGroups[i][1];
 
		// Mientras queden vacas en el grupo actual y se puedan
		// colocar en la cima de la cola, procesar
		while (!towers.empty() && towers[0][0] >= (cowGroups[i][0] + k) && amt > 0) {
			if (towers[0][1] > amt) {
				towers[0][1] -= amt;
				amt = 0;
				break;
			} else {
				amt -= towers[0][1];
				towers.pop_front();
			}
		}
 
		towers.push_back({cowGroups[i][0], cowGroups[i][1] - amt});
		count += cowGroups[i][1] - amt;
	}
 
	cout << count << '\n';
}
from collections import deque
 
n, m, k = map(int, input().split())
 
pairs = []
for _ in range(n):
	w, a = map(int, input().split())
	pairs.append([w, a])
pairs.sort(reverse=True)
# Ordenar por peso decreciente
 
towers = deque()
# Cola que guarda vacas según pares de peso y cantidad
towers.append([1e100, m])
# Usar un valor grande para la torre inicial
 
answer = 0
for w, a in pairs:
	remaining = a
	# Mientras queden vacas en el grupo actual y se puedan
	# colocar en la cima de la cola, procesar
	while len(towers) > 0 and remaining > 0 and w + k <= towers[0][0]:
		if towers[0][1] > remaining:
			towers[0][1] -= remaining
			remaining = 0
		else:
			remaining -= towers[0][1]
			towers.popleft()
	count = a - remaining
	if count > 0:
		towers.append([w, count])
		answer += count
 
print(answer)
import java.io.*;
import java.util.*;
 
public class Main {
	static class Group {
		final long weight;
		final long amount;
 
		Group(long weight, long amt) {
			this.weight = weight;
			this.amount = amt;
		}
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(read.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
 
		Group[] cowGroups = new Group[n];
 
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(read.readLine());
			long w = Integer.parseInt(st.nextToken());
			long a = Integer.parseInt(st.nextToken());
			cowGroups[i] = new Group(w, a);
		}
 
		Arrays.sort(cowGroups, Comparator.comparingLong(Group -> Group.weight));
		// Ordenar por peso decreciente
 
		// Cola que guarda vacas según pares de peso y cantidad
		Deque<long[]> towers = new ArrayDeque<>();
		towers.addFirst(new long[] {(long)-1e18, m});
		// Usar un valor grande para la torre inicial
		long answer = 0;
 
		for (Group p : cowGroups) {
			long w = p.weight;
			long a = p.amount;
			long remaining = a;
			// Mientras queden vacas en el grupo actual y se puedan
			//  colocar en la cima de la cola, procesar
			while (!towers.isEmpty() && remaining > 0 &&
			       w - k >= towers.peekFirst()[0]) {
				long[] top = towers.peekFirst();
				if (top[1] > remaining) {
					top[1] -= remaining;
					remaining = 0;
				} else {
					remaining -= top[1];
					towers.pollFirst();
				}
			}
 
			long cowsUsed = a - remaining;
			if (cowsUsed > 0) {
				towers.addLast(new long[] {w, cowsUsed});
				answer += cowsUsed;
			}
		}
 
		System.out.println(answer);
	}
}
Fundamentos