Overview

This is a problem where, given customers’ budgets, ticket prices, and a maximum sales limit for each ticket, we need to determine how many customers can be sold tickets when serving them in order.

Analysis

In this problem, for each customer, we select “the most expensive ticket within their budget,” and sell it only if that ticket has not yet been sold \(K\) or more times.

Key Observations

• For each customer, we need to select the most expensive ticket they can afford.
• Since all ticket prices are distinct, such a ticket is uniquely determined.
• We must not exceed the sales limit (\(K\) tickets) for any ticket.

What About a Naive Approach?

If we search linearly for the appropriate ticket each time, the worst case becomes \(O(NM)\), which is too slow for \(N, M \sim 2 \times 10^5\).

Also, if we simply assign tickets in order from cheapest, we may fail to satisfy customers who want expensive tickets, potentially reducing the total number of tickets sold.

Solution

By sorting the ticket price list \(G\) in advance, we can efficiently find the highest-priced ticket within each customer’s budget using binary search.

Furthermore, by tracking the sales count for each ticket, we can ensure the sales limit is not exceeded.

Algorithm

1. Sort the ticket price list \(G\) in ascending order.
2. For each customer’s budget \(S_i\), do the following:
   • Use binary search (bisect_right) to find the index of the ticket with the “highest price that is at most \(S_i\).”
   • If the current sales count of that ticket is less than \(K\), sell one ticket and increment the sales count.
   • If a sale is made, increment the result counter.
3. After processing all customers, output the number of customers who were sold tickets.

Example

For instance, consider: - Customer budgets: \([5, 10, 15]\) - Ticket prices: \([3, 7, 9, 12]\), \(K=1\)

In this case: - Customer 1 (budget 5) → The most expensive affordable ticket is 3 → Available for sale → Sales count becomes 1 → Success - Customer 2 (budget 10) → The most expensive affordable ticket is 9 → Available for sale → Sales count becomes 1 → Success - Customer 3 (budget 15) → The most expensive affordable ticket is 12 → Sales count is still 0, so OK → Success

Therefore, the answer is 3 customers.

Complexity

• Time complexity: \(O((N + M) \log M)\)
  • Sorting takes \(O(M \log M)\)
  • Binary search and processing for each customer takes \(O(N \log M)\)
• Space complexity: \(O(M + N)\)
  • For the ticket price list, customer list, sales count management dictionary, etc.

Implementation Notes

• By using bisect.bisect_right(G, s), we can efficiently obtain the position of the largest element that is at most \(s\).

• By using defaultdict(int), we can treat the initial sales count as 0.

• It is important to strictly enforce the sales limit for each ticket — if the limit is exceeded, the ticket must not be sold.

  Source Code

import bisect
from collections import defaultdict
import sys

input = sys.stdin.read

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N, M, K = map(int, data[:3])
    S = list(map(int, data[3:3+N]))
    G = list(map(int, data[3+N:3+N+M]))
    
    # Sort ticket prices
    G.sort()
    
    # Count of tickets sold per type
    sold_count = defaultdict(int)
    
    res = 0
    
    for s in S:
        # Binary search for the most expensive ticket <= s
        idx = bisect.bisect_right(G, s) - 1
        if idx >= 0:
            best_ticket = G[idx]
            if sold_count[best_ticket] < K:
                sold_count[best_ticket] += 1
                res += 1
            # else: do nothing, cannot sell
        # else: no ticket affordable, do nothing
    
    print(res)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.