D - パソコンの販売 / Selling Computers Editorial by admin
Gemini 3.8 Flash (High)Overview
This problem can be solved using a greedy approach: sort both the customers and the computers in descending order of performance, and for each customer in order of strictest performance requirement, pick the highest-priced computer that the customer can purchase using a priority queue (heap).
Analysis
1. Checking Trivial Cases
First, if \(N < M\) (there are more customers than computers), it is impossible to sell a distinct computer to every customer, so immediately output -1.
2. Why Consider Customers with Higher Requirements First?
The breadth of computer options varies from customer to customer: - Customers with higher required performance \(C_j\): have fewer computers to choose from (stricter condition). - Customers with lower required performance \(C_j\): have more computers to choose from (more relaxed condition).
Customers with low requirements can purchase either high-end or low-end computers, whereas customers with high requirements can only purchase high-end computers. Therefore, we must prioritize assigning computers to customers with high requirements, whose choices are more constrained.
3. Inclusion Property of Choices and the Greedy Approach
Consider sorting the customers in descending order of required performance (\(C_1 \ge C_2 \ge \dots \ge C_M\)).
If \(S_j = \{ i \mid A_i \ge C_j \}\) denotes the set of computers that customer \(j\) can purchase, the following inclusion relation holds: $\(S_1 \subseteq S_2 \subseteq \dots \subseteq S_M\)$ In other words, as we process the customers in order, the choices of purchasable computers only increase, and a computer that becomes eligible once will never become ineligible later.
From this property, the following greedy approach is justified:
- When considering customer \(j\), add all computers not yet in the candidate pool whose performance is at least \(C_j\) into the pool.
- Assign the highest-priced computer from the candidate pool to customer \(j\).
- This is because all computers currently in the pool can also be purchased by any subsequent customer (who has a more relaxed requirement), so committing the most expensive available computer to customer \(j\) does not disadvantage future customers or hurt our ability to maximize total revenue.
- If the candidate pool is empty, no computer satisfies customer \(j\)’s condition, so it is impossible to sell to all customers (output -1).
Concrete Example
- Computers: \(P_1(\text{performance } 10, \text{price } 100), P_2(\text{performance } 10, \text{price } 50), P_3(\text{performance } 5, \text{price } 200)\)
- Customers: \(K_1(\text{requirement } 10), K_2(\text{requirement } 5)\)
- Processing \(K_1\) (requirement 10):
- The computers with performance at least 10 are \(P_1(100)\) and \(P_2(50)\). Add them to the pool.
- Assign the most expensive computer in the pool, \(P_1(100)\), to \(K_1\). (Remaining in pool: \(P_2(50)\))
- Processing \(K_2\) (requirement 5):
- Add the computer \(P_3(200)\) with performance at least 5 to the pool. (Pool: \(P_2(50), P_3(200)\))
- Assign the most expensive computer, \(P_3(200)\), to \(K_2\).
- Result: \(100 + 200 = 300\), achieving the maximum revenue.
Algorithm
- If \(N < M\), output
-1and terminate. - Sort the computers in descending order of performance \(A_i\).
- Sort the customers in descending order of required performance \(C_j\).
- Prepare a max-heap to manage prices (in Python, a min-heap storing negated prices).
- Iterate through each customer \(c \in C\) in descending order of required performance:
- Add all computers not yet added to the heap that have performance at least \(c\) to the heap.
- If the heap is empty, there is no computer that can be sold to this customer, so output
-1and terminate. - Pop the maximum price from the heap and add it to the total revenue.
- After assigning computers to all customers, output the total revenue.
Complexity
Time Complexity: \(O(N \log N + M \log M)\)
- Sorting computers: \(O(N \log N)\)
- Sorting customers: \(O(M \log M)\)
- Since each computer is pushed to the heap at most once, the total time for heap insertions is \(O(N \log N)\)
- Extracting the maximum value from the heap for each customer takes \(O(M \log N)\)
- Overall, the time complexity is \(O(N \log N + M \log M)\), which is well fast enough for \(N, M \le 10^5\).
Space Complexity: \(O(N + M)\)
- Storing the computer and customer data, along with the heap, uses at most \(O(N + M)\) memory (with the heap using at most \(O(N)\) space).
Implementation Details
Using a Priority Queue (Max-Heap): Python’s
heapqmodule provides a min-heap by default. Therefore, multiplying prices by-1before inserting them allows the heap to function as a max-heap.Scanning Computers with Two Pointers: By maintaining an index
pc_idxto scan through the computer list and ensuring that computers already pushed to the heap are not revisited, the total time spent scanning computers is bounded by \(O(N)\).Fast I/O: Since the input size is large (\(N, M \le 10^5\)), reading the entire input at once using
sys.stdin.read().split()prevents I/O bottlenecks.Source Code
import sys
import heapq
def main():
input_data = sys.stdin.read().split()
if not input_data:
return
N = int(input_data[0])
M = int(input_data[1])
if N < M:
print(-1)
return
pcs = [(int(input_data[i]), int(input_data[i+1])) for i in range(2, 2 + 2 * N, 2)]
C = [int(x) for x in input_data[2 + 2 * N : 2 + 2 * N + M]]
pcs.sort(key=lambda x: x[0], reverse=True)
C.sort(reverse=True)
heap = []
pc_idx = 0
total_sales = 0
for c in C:
while pc_idx < N and pcs[pc_idx][0] >= c:
heapq.heappush(heap, -pcs[pc_idx][1])
pc_idx += 1
if not heap:
print(-1)
return
total_sales += -heapq.heappop(heap)
print(total_sales)
if __name__ == '__main__':
main()
This editorial was generated by gemini-3.8-flash-high.