Official Editorial

Explanation

Universal ports are more flexible than restricted ones, since they can accept either type. Thus, we should prioritize restricted ports over universal ports.

If we assign a mouse that could've gone to a restricted port to a universal port, we might later on be forced to use a more expensive mouse for that restricted port.

Greedy Algorithm

• Sort all mice by cost
• For each mouse:

  • If a matching restricted port is available, use it
  • Otherwise, use a universal port (if available)
• After all restricted ports are filled, assign the cheapest remaining mice to universal ports

This prioritizes filling restricted ports first and delays using universal ports. If we ever assigned a cheap mouse to a universal port while a more expensive mouse of the same type occupies a restricted port, we could swap them without increasing cost, so an optimal solution always has restricted ports filled first with the cheapest valid mice, and universal ports used only afterward.

Implementation

Time Complexity: $\mathcal{O}(M \log M)$

Copy
#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;

Solution 2 (Two Pointers)

Explanation

An alternate approach uses two pointers instead of a greedy algorithm. The idea is that any optimal construction will use the $L$ cheapest USB mice and $R$ cheapest PS2 mice. Since having more USB mice gives less flexibility for PS2 mice, we iterate on each value of $L$, and find the maximum value of $R$ and the cost using two pointers. Given that it's two pointers, we know that the value of $R$ monotonically decreases as $L$ increases, meaning that our pointers move at most $\mathcal{O}(M)$ times.

Implementation

Time Complexity: $\mathcal{O}(M \log M)$

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int A, B, C;  // A = USB ports, B = PS/2 ports, C = universal ports
	cin >> A >> B >> C;