Skip to Content
CTRL K

USB vs PS/2

Editorial oficial 

Explicación

Los puertos universales son más flexibles que los restringidos, porque aceptan cualquiera de los dos tipos. Por lo tanto, hay que priorizar los puertos restringidos sobre los universales.

Si asignamos un mouse que podría haber ido a un puerto restringido a un puerto universal, más adelante podríamos vernos forzados a usar un mouse más caro para ese puerto restringido.

Algoritmo voraz

  • Ordenamos todos los mice por costo
  • Para cada mouse:
    • Si hay un puerto restringido compatible disponible, lo usamos
    • Si no, usamos un puerto universal (si hay)
  • Después de llenar todos los puertos restringidos, asignamos los mice restantes más baratos a los puertos universales

Esto prioriza llenar primero los puertos restringidos y retrasa el uso de los universales. Si alguna vez asignáramos un mouse barato a un puerto universal mientras un mouse más caro del mismo tipo ocupa un puerto restringido, podríamos intercambiarlos sin aumentar el costo, así que una solución óptima siempre llena primero los puertos restringidos con los mice válidos más baratos, y usa los puertos universales solo después.

Implementación

Complejidad temporal: O(Mlog⁡M)\mathcal{O}(M \log M)

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int usbPorts, ps2Ports, universalPorts;
	cin >> usbPorts >> ps2Ports >> universalPorts;
 
	int m;
	cin >> m;
 
	vector<long long> usbCosts, ps2Costs;
 
	for (int i = 0; i < m; i++) {
		long long cost;
		string type;
		cin >> cost >> type;
 
		if (type == "USB") {
			usbCosts.push_back(cost);
		} else {
			ps2Costs.push_back(cost);
		}
	}
 
	sort(usbCosts.begin(), usbCosts.end());
	sort(ps2Costs.begin(), ps2Costs.end());
 
	long long totalCost = 0;
	int totalMice = 0;
 
	vector<long long> remaining;
 
	// Llenamos los puertos solo USB
	for (int i = 0; i < min((int)usbCosts.size(), usbPorts); i++) {
		totalCost += usbCosts[i];
		totalMice++;
	}
 
	for (int i = usbPorts; i < (int)usbCosts.size(); i++) {
		remaining.push_back(usbCosts[i]);
	}
 
	// Llenamos los puertos solo PS/2
	for (int i = 0; i < min((int)ps2Costs.size(), ps2Ports); i++) {
		totalCost += ps2Costs[i];
		totalMice++;
	}
 
	for (int i = ps2Ports; i < (int)ps2Costs.size(); i++) {
		remaining.push_back(ps2Costs[i]);
	}
 
	// Usamos los puertos universales
	sort(remaining.begin(), remaining.end());
 
	for (int i = 0; i < min((int)remaining.size(), universalPorts); i++) {
		totalCost += remaining[i];
		totalMice++;
	}
 
	cout << totalMice << " " << totalCost << "\n";
}

Solución 2 (Dos punteros)

Explicación

Un enfoque alternativo usa dos punteros en lugar de un algoritmo voraz. La idea es que cualquier construcción óptima usará los LL mice USB más baratos y los RR mice PS2 más baratos. Como tener más mice USB da menos flexibilidad para los mice PS2, iteramos sobre cada valor de LL y hallamos el valor máximo de RR y el costo usando dos punteros. Como son dos punteros, sabemos que el valor de RR decrece de forma monótona a medida que LL aumenta, lo que significa que nuestros punteros se mueven a lo sumo O(M)\mathcal{O}(M) veces.

Implementación

Complejidad temporal: O(Mlog⁡M)\mathcal{O}(M \log M)

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int A, B, C;  // A = puertos USB, B = puertos PS/2, C = puertos universales
	cin >> A >> B >> C;
 
	int M;
	cin >> M;
 
	vector<long long> usb, ps2;
 
	// Separamos los mice por tipo
	for (int i = 0; i < M; i++) {
		long long cost;
		string type;
		cin >> cost >> type;
		if (type == "USB") usb.push_back(cost);
		else ps2.push_back(cost);
	}
 
	// Ordenamos costos para tomar siempre primero los más baratos
	sort(usb.begin(), usb.end());
	sort(ps2.begin(), ps2.end());
 
	int R = ps2.size();  // cantidad actual de mice PS/2 tomados
	long long sum = 0;
 
	// Inicialmente tomamos todos los mice PS/2
	for (auto x : ps2) sum += x;
 
	// (cantidad de mice, costo negativo) para el máximo lexicográfico
	pair<int, long long> ans = {0, 0};
 
	// Probamos tomar L mice USB
	for (int L = 0; L <= (int)usb.size(); L++) {
		// Agregamos el siguiente mouse USB (si L > 0)
		if (L > 0) sum += usb[L - 1];
 
		// Chequeamos si el (L, R) actual cabe en los puertos disponibles
		auto can_form = [&]() {
			return L <= A + C &&        // USB + universal pueden manejar los mice USB
			       R <= B + C &&        // PS/2 + universal pueden manejar los mice PS/2
			       L + R <= A + B + C;  // restricción de puertos totales
		};
 
		bool bad = false;
 
		// Si no es factible, reducimos R (sacamos los mice PS/2 más caros)
		while (!can_form()) {
			if (R == 0) {
				bad = true;
				break;
			}
			R--;
			sum -= ps2[R];  // quitamos el mayor costo PS/2 restante
		}
 
		if (bad) break;
 
		// Maximizamos la cantidad de mice y luego minimizamos el costo
		ans = max(ans, {L + R, -sum});
	}
 
	cout << ans.first << " " << -ans.second << "\n";
}
Fundamentos