D - パソコンの販売 / Selling Computers Editorial by admin Editorial for printing
gpt-6-astra-mediumOverview
Process customers in descending order of their required performance, selling each customer the most expensive unsold computer that meets their requirement. This greedy approach can be implemented efficiently using sorting and a priority queue (heap).
Analysis
Processing customers with higher required performance first
Customers with lower performance requirements can purchase a wider variety of computers, whereas customers with higher performance requirements have fewer options.
For example, suppose there are the following \(2\) computers:
| Performance | Price |
|---|---|
| \(10\) | \(100\) |
| \(5\) | \(50\) |
If there are two customers with requirements \(5\) and \(10\), and we sell the most expensive computer to the customer with requirement \(5\) first, we will no longer be able to sell a computer to the customer with requirement \(10\).
Therefore, we consider processing customers in descending order of their required performance.
We can pick the most expensive valid computer
Let \(c\) be the performance requirement of the current customer. Since the remaining customers are sorted in descending order of requirement, all remaining customers have requirements less than or equal to \(c\).
Therefore, any computer that can be sold to the current customer can also be sold to any of the remaining customers.
From this property, it is always optimal to choose the most expensive unsold computer that can be sold to the current customer. This can be justified by an exchange argument.
Consider an optimal assignment consistent with our choices so far. Let \(x\) be the computer assigned to the current customer in this optimal assignment, and let \(y\) be the most expensive valid computer chosen by our greedy strategy.
- If \(y\) is already assigned to the current customer, we do nothing.
- If \(y\) is not assigned to anyone, we can replace \(x\) with \(y\). Since \(B_y \ge B_x\), the total revenue does not decrease.
- If \(y\) is assigned to a later customer, we can swap their computers: sell \(y\) to the current customer and \(x\) to that later customer. Since \(x\) satisfies the current customer’s requirement, it also satisfies the requirement of the later customer (whose required performance is at most that of the current customer). The total revenue remains unchanged.
Thus, the greedy strategy of picking the most expensive valid computer at each step achieves the maximum revenue.
Speeding up the management of candidate computers
If we check all computers for each customer, the time complexity would be \(O(NM)\), which requires around \(10^{10}\) operations in the worst case.
To avoid this, we also sort the computers in descending order of performance.
Since the customers’ required performance decreases as we process them, the set of available computers that meet the requirement monotonically grows. By adding only newly qualified computers to a heap, we do not need to check all computers every time.
We store the prices of candidate computers in a heap so that we can extract the highest price efficiently.
Algorithm
- If \(N < M\), output \(-1\) because there are not enough computers.
- Sort the computers in descending order of performance \(A_i\).
- Sort the customers in descending order of required performance \(C_j\).
- Initialize an empty heap, a total revenue
total = 0, and an indexipointing to the first computer that has not yet been added to the heap. - For each customer with required performance
requirement, do the following:- While the performance of
computers[i]is greater than or equal torequirement, push its price into the heap and incrementi. - If the heap is empty, there is no unsold computer that can be sold to this customer, so output \(-1\) and terminate.
- Pop the maximum price from the heap and add it to
total.
- While the performance of
- If computers have been sold to all customers, output
total.
When processing each customer, after the insertion step, the heap contains all “unsold computers that can be sold to this customer”. Since a sold computer is removed from the heap, no computer will be sold to multiple customers.
Furthermore, from the exchange argument, our greedy choices do not prevent us from achieving a valid assignment for all customers if one existed. Therefore, if the heap becomes empty at any point, we can conclude that it is impossible to sell computers to all customers.
Complexity
- Time complexity: \(O(N \log N + M \log M + (N+M)\log N)\)
- Space complexity: \(O(N+M)\)
Sorting the computers and customers takes \(O(N \log N)\) and \(O(M \log M)\) time, respectively. Each computer is pushed into the heap at most once, and an element is popped from the heap once per customer.
Note that since the process terminates early when \(N < M\), we have \(M \le N\) whenever the loop continues, so the time complexity can also be expressed as \(O(N \log N)\).
Implementation Notes
Python’s
heapqis a min-heap.
By pushing \(-B_i\) instead of \(B_i\), we can extract elements in descending order of price. In the code,total -= pop(heap)adds the original price to the revenue.A computer can be sold even if its performance is equal to the requirement.
The condition for adding to the heap iscomputers[i][0] >= requirement.Do not clear the heap for each customer.
A computer that was valid for a previous customer is also valid for all subsequent customers. Candidates that were not chosen should remain in the heap for future use.The total revenue can be up to \(10^{14}\).
While Python handles arbitrarily large integers automatically, other languages require using a \(64\)-bit integer (e.g.,long longin C++).Source Code
import sys
import heapq
def main():
data = list(map(int, sys.stdin.buffer.read().split()))
n, m = data[0], data[1]
if n < m:
print(-1)
return
end = 2 + 2 * n
computers = [(data[i], data[i + 1]) for i in range(2, end, 2)]
customers = data[end:end + m]
del data
computers.sort(reverse=True)
customers.sort(reverse=True)
heap = []
push = heapq.heappush
pop = heapq.heappop
total = 0
i = 0
for requirement in customers:
while i < n and computers[i][0] >= requirement:
push(heap, -computers[i][1])
i += 1
if not heap:
print(-1)
return
total -= pop(heap)
print(total)
if __name__ == "__main__":
main()
This editorial was generated by gpt-6-astra-medium.
posted:
last update: