Every copy counts
Use multisets to represent stock and sell exactly one affordable item.
Multiplicity changes the model
A multiset retains repeated copies. For {2, 5, 5, 5, 7}, size() is 5 and count(5) is 3. Each insert creates a new entry and returns an iterator; unlike set insertion, it does not return a pair with a new-key flag.
find(x) locates a matching occurrence, without promising the first one in an equal run. lower_bound(x) finds the run’s beginning. equal_range(x) returns lower and upper bounds, whose half-open interval contains every matching copy.
Erase one copy or all copies deliberately
bag.erase(x) removes every copy matching key x. To remove one occurrence, find x, verify the iterator is not end(), then erase that iterator. Empty bags and absent values require no removal.
For k equal copies in n stored entries, count(x) and erase(x) may cost O(log(n + 1) + k). Repeatedly counting a huge equal run can become quadratic overall. Use contains for existence, or a frequency map when direct count queries are the main task.
Worked pattern: the ticket office
The rule is to serve customers in input order, selling the most expensive remaining ticket within each budget. upper_bound(budget) separates affordable prices from prices that are too large. Its guarded predecessor is the answer; erase that one iterator to preserve other equal-price tickets.
Before each customer, the multiset contains exactly the unsold tickets. This invariant explains both selection and removal. Building and processing q customers takes O((n + q)(1 + log(n + 1))) time and O(n) ticket storage.
// Complete C++23 program. Input: n q, n positive prices, q budgets.
#include <iostream>
#include <set>
int main() {
int n, q;
std::cin >> n >> q;
std::multiset<int> prices;
for (int i = 0; i < n; ++i) {
int price;
std::cin >> price;
prices.insert(price);
}
while (q--) {
int budget;
std::cin >> budget;
auto it = prices.upper_bound(budget);
if (it == prices.begin()) std::cout << -1 << '\n';
else {
--it;
std::cout << *it << '\n';
prices.erase(it);
}
}
}Set & multiset
Both containers keep values sorted. Erase one removes a single occurrence, like erase(iterator).
3 stored items · 3 distinct values
Guided simulation · Change the inputs to test your understanding.
Tickets cost 4, 4, 9. Three customers each have budget 4. What should the outputs be?
Turn the idea into code
A multiset has 100000 copies of 5. Explain why calling count(5) once for every stored copy can be far slower than O(n log n).
Give me a hint
Count the matching entries visited by one count call, then count how many calls are made.
Show the explained solution
Each count may traverse all 100000 matching copies, and there are 100000 calls. That is O(n²) work. Store 5 → 100000 in a frequency map if the required operation is repeatedly reading the number of copies.
Your notes
Mark complete when you can explain it yourself.