Cow Dance Show

Explicación

Hay dos partes para resolver este problema. Primero, necesitamos determinar de forma eficiente si un valor dado de $K$ es válido. Segundo, necesitamos hallar de forma eficiente el menor $K$ que sea válido.

Empezamos determinando si un $K$ dado es válido. Podemos simular a las vacas bailando en el escenario y luego saliendo, y cuando hay $K$ vacas en el escenario, queremos hallar el momento más temprano en que una vaca deja el escenario (cuando la siguiente vaca puede entrar). Esto motiva usar una cola de prioridad, que admite inserción y extracción eficiente de su elemento mínimo. Por lo tanto, comprobar si $K$ es válido toma $\mathcal{O}(N\log K)$ tiempo.

Ahora, queremos determinar el valor mínimo de $K$ que es válido. Recordemos que $K=N$ está garantizado como un valor válido.

Observemos que si $K$ es válido, entonces también lo es $K+1$ , ya que tener un lugar extra no puede hacer que las vacas bailen más tarde de lo que lo harían originalmente. Por lo tanto, podemos hacer búsqueda binaria del menor $K$ de ese tipo, lo cual es lo suficientemente rápido para resolver el problema.

Implementación

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

C++PythonJava


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	freopen("cowdance.in", "r", stdin);
	freopen("cowdance.out", "w", stdout);
 
	int n, t;
	cin >> n >> t;
	int ar[n];
 
	for (int i = 0; i < n; i++) { cin >> ar[i]; }
 
	int hi = n, lo = 1;
	int sol = n;
 
	while (lo <= hi) {
		int mid = lo + (hi - lo) / 2;
		int time = 0, j = 0;
		priority_queue<int> pq;
		int size = 0;
		while (size < mid && j < n) {
			pq.push(-ar[j]);
			size++;
			j++;
		}
 
		while ((int)pq.size()) {
			time += max(0, -pq.top() - time);
			pq.pop();
			if (j < n) {
				pq.push(-(ar[j] + time));
				j++;
			}
		}
 
		if (time > t) {
			lo = mid + 1;
		} else {
			sol = min(sol, mid);
			hi = mid - 1;
		}
	}
 
	cout << sol << '\n';
}


import heapq
 
with open("cowdance.in") as r:
	n, maximum = map(int, r.readline().split())
	dance = [int(r.readline()) for _ in range(n)]
 
left = 1
right = n + 1
while left < right:
	mid = (left + right) // 2
	parts = dance[:mid]
	heapq.heapify(parts)
 
	for i in range(mid, n):
		exit_stage_time = heapq.heappop(parts) + dance[i]
		heapq.heappush(parts, exit_stage_time)
 
	if maximum < max(parts):
		left = mid + 1
	else:
		right = mid
 
print(left, file=open("cowdance.out", "w"))


import java.io.*;
import java.util.*;
 
public class CowDanceShow {
	static int[] danceTimes;
	static int n;
	static int maxTime;
 
	static boolean isOk(int stageSize) {
		PriorityQueue<Integer> currentDancing = new PriorityQueue<>();
 
		for (int x = 0; x < n; x++) {
			if (currentDancing.size() < stageSize) {
				currentDancing.add(danceTimes[x]);
			} else {
				// agregamos la siguiente vaca de la fila a la que terminará primero
				currentDancing.add(currentDancing.remove() + danceTimes[x]);
			}
		}
 
		int lastFinish = Integer.MAX_VALUE;
 
		while (currentDancing.size() > 0) { lastFinish = currentDancing.remove(); }
		return lastFinish <= maxTime;
	}
 
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("cowdance");
		n = io.nextInt();
		maxTime = io.nextInt();
		danceTimes = new int[n];
 
		for (int x = 0; x < n; x++) { danceTimes[x] = io.nextInt(); }
 
		int low = 1;   // el mínimo es que solo quepa una vaca
		int high = n;  // el máximo necesario es que quepan todas las vacas a la vez
 
		while (low < high) {
			int mid = (low + high) / 2;
			if (isOk(mid)) {
				high = mid;
			} else {
				low = mid + 1;
			}
		}
		io.println(low);
		io.close();
	}
 
	// CodeSnip{Kattio}
}