Milk Measurement

Solución 1 - Mapa ordenado

Primero, como el número de mediciones es grande, las ordenamos por día. Cada vez que procesamos una medición, rastreamos la vaca cuya producción cambia, además de las producciones vieja y nueva. Después, comprobamos si las vacas con producción máxima cambiaron.

Para esto, hay que verificar varias condiciones. Por ejemplo, si el número de vacas con la producción máxima cambió, entonces el display hay que actualizarlo. Sin embargo, el número de vacas podría quedarse igual y aun así el display podría necesitar actualización.

Para comprobarlo, verificamos si la vaca actual estaba originalmente en el display, y si sigue ahí después de que cambia la medición.

Implementación

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

C++JavaPython


#include <algorithm>
#include <fstream>
#include <iostream>
#include <map>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
struct Log {
	int day, cow, change;
};
 
int main() {
	std::ifstream read("measurement.in");
 
	int n;
	int g;
	read >> n >> g;
 
	vector<Log> log(n);
	std::map<int, int> cows;
	for (Log &l : log) {
		read >> l.day >> l.cow >> l.change;
		cows[l.cow] = g;
	}
	std::sort(log.begin(), log.end(),
	          [](const Log &l1, const Log &l2) { return l1.day < l2.day; });
 
	std::map<int, int> milk_prod{{g, n}};
 
	int change_amt = 0;
	for (Log l : log) {
		int milk_amt = cows[l.cow];
		bool was_top = milk_amt == milk_prod.rbegin()->first;
		int prev_count = milk_prod[milk_amt];
		// quitamos el número anterior de producción de leche
		milk_prod[milk_amt]--;
		if (milk_prod[milk_amt] == 0) { milk_prod.erase(milk_amt); }
 
		// actualizamos las cantidades de producción de leche
		milk_amt += l.change;
		cows[l.cow] = milk_amt;
		milk_prod[milk_amt]++;
 
		bool is_top = milk_amt == milk_prod.rbegin()->first;
		int curr_count = milk_prod[milk_amt];
		if (was_top) {
			if (is_top && curr_count == prev_count) { continue; }
			/*
			 * si era la más alta y ahora no lo es o ahora hay
			 * varias vacas con el máximo, entonces FJ tiene que cambiar el retrato
			 */
			change_amt++;
		} else if (is_top) {
			/*
			 * si no estaba en el máximo pero ahora sí,
			 * entonces FJ también tiene que cambiar el retrato
			 */
			change_amt++;
		}
	}
 
	std::ofstream("measurement.out") << change_amt << endl;
}


import java.io.*;
import java.util.*;
 
public class Measurement {
	// BeginCodeSnip{Log Class}
	private static class Log {
		int day, cow, change;
		public Log(int day, int cow, int change) {
			this.day = day;
			this.cow = cow;
			this.change = change;
		}
	}
	// EndCodeSnip
 
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("measurement");
		int n = io.nextInt();
		int g = io.nextInt();
 
		Log[] log = new Log[n];
		Map<Integer, Integer> cows = new HashMap<>();
		for (int i = 0; i < n; i++) {
			log[i] = new Log(io.nextInt(), io.nextInt(), io.nextInt());
			cows.put(log[i].cow, g);
		}
		Arrays.sort(log, Comparator.comparingInt(o -> o.day));
 
		// contiene la tabla de frecuencias de producción de leche en orden creciente
		TreeMap<Integer, Integer> milkProd = new TreeMap<>();
		milkProd.put(g, n);
 
		int changeAmt = 0;
		for (Log l : log) {
			int milkAmt = cows.get(l.cow);
			boolean wasTop = milkAmt == milkProd.lastKey();
			int prevCount = milkProd.get(milkAmt);
 
			// quitamos el número anterior de producción de leche
			milkProd.put(milkAmt, milkProd.get(milkAmt) - 1);
			if (milkProd.get(milkAmt) == 0) { milkProd.remove(milkAmt); }
 
			// actualizamos las cantidades de producción de leche
			milkAmt += l.change;
			cows.put(l.cow, milkAmt);
			milkProd.put(milkAmt, milkProd.getOrDefault(milkAmt, 0) + 1);
 
			boolean isTop = milkAmt == milkProd.lastKey();
			int currCount = milkProd.get(milkAmt);
			if (wasTop) {
				if (isTop && currCount == prevCount) { continue; }
				/*
				 * si era la más alta y ahora no lo es o ahora hay
				 * varias vacas con el máximo, entonces FJ tiene que cambiar el retrato
				 */
				changeAmt++;
			} else if (isTop) {
				/*
				 * si no estaba en el máximo pero ahora sí,
				 * entonces FJ también tiene que cambiar el retrato
				 */
				changeAmt++;
			}
		}
 
		io.println(changeAmt);
		io.close();
	}
 
	// CodeSnip{Kattio}
}


import bisect
 
with open("measurement.in", "r") as read:
	n, g = map(int, read.readline().split())
	measurements = [list(map(int, read.readline().split())) for i in range(n)]
	# ordenamos por día
	measurements.sort()
 
# mantenemos una lista ordenada y un diccionario de producciones de las vacas
sorted_list = []
cows = list(set([x[1] for x in measurements]))
values = dict()
for i in range(len(cows)):
	values[cows[i]] = g
	sorted_list.append([g, cows[i]])
 
changes = 0
sorted_list.append([g, float("inf")])
top_cows = sorted(set(cows + [float("inf")]))
for i in range(n):
	day, cow, change = map(int, measurements[i])
 
	# hallamos el índice a actualizar usando bisect
	index = bisect.bisect_left(sorted_list, [values[cow], cow])
 
	# mantenemos el orden ordenado
	sorted_list.pop(index)
	bisect.insort(sorted_list, [values[cow] + change, cow])
	values[cow] += change
 
	# hallamos la producción más alta
	highest_output = sorted_list[-1][0]
 
	# hallamos las vacas con la producción más alta
	top_cows2 = []
	for j in range(len(sorted_list) - 1, -1, -1):
		if sorted_list[j][0] == highest_output:
			top_cows2.append(sorted_list[j][1])
		else:
			break
	top_cows2.sort()
	if top_cows != top_cows2:
		top_cows = top_cows2
		changes += 1
 
print(changes, file=open("measurement.out", "w"))

Solución 2 - Cola de prioridad

Un método alternativo para llevar la cuenta de la producción máxima de leche es usar una cola de prioridad en vez de un mapa ordenado. Todos los mapas ordenados del código de la solución de arriba se pueden dejar como están o intercambiar por tablas hash.

Implementación

C++


#include <algorithm>
#include <cassert>
#include <fstream>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
 
using std::endl;
using std::vector;
 
struct Log {
	int day, cow, change;
};
 
int main() {
	std::ifstream read("measurement.in");
 
	int n;
	int g;
	read >> n >> g;
 
	vector<Log> log(n);
	std::unordered_map<int, int> cows;  // o std::map
	for (Log &l : log) {
		read >> l.day >> l.cow >> l.change;
		cows[l.cow] = g;
	}
	std::sort(log.begin(), log.end(),
	          [](const Log &l1, const Log &l2) { return l1.day < l2.day; });
 
	std::unordered_map<int, int> milk_prod{{g, n}};
	std::priority_queue<int> possible_maxes;
	possible_maxes.push(g);
	auto query_max = [&]() -> int {
		while (true) {
			assert(!possible_maxes.empty());
			if (milk_prod.count(possible_maxes.top())) break;
			possible_maxes.pop();
		}
		return possible_maxes.top();
	};
 
	int change_amt = 0;
	for (Log l : log) {
		int milk_amt = cows[l.cow];
		bool was_top = milk_amt == query_max();
		int prev_count = milk_prod[milk_amt];
		// quitamos el número anterior de producción de leche
		milk_prod[milk_amt]--;
		if (milk_prod[milk_amt] == 0) { milk_prod.erase(milk_amt); }
 
		// actualizamos las cantidades de producción de leche
		milk_amt += l.change;
		cows[l.cow] = milk_amt;
		milk_prod[milk_amt]++;
		possible_maxes.push(milk_amt);
 
		bool is_top = milk_amt == query_max();
		int curr_count = milk_prod[milk_amt];
		if (was_top) {
			if (is_top && curr_count == prev_count) { continue; }
			/*
			 * si era la más alta y ahora no lo es o ahora hay
			 * varias vacas con el máximo, entonces FJ tiene que cambiar el retrato
			 */
			change_amt++;
		} else if (is_top) {
			/*
			 * si no estaba en el máximo pero ahora sí,
			 * entonces FJ también tiene que cambiar el retrato
			 */
			change_amt++;
		}
	}
 
	std::ofstream("measurement.out") << change_amt << endl;
}