D - パソコンの販売 / Selling Computers Editorial by admin Editorial for printing
gpt-6-astra-mediumOverview
In this problem, we want to assign a distinct computer satisfying the required performance to each customer and maximize the total selling price.
It can be solved using a greedy approach: process customers in descending order of their required performance, and for each customer, choose the most expensive unsold computer that can be sold to them.
Analysis
Processing customers in descending order of required performance
If we freely assign computers starting from customers with lower required performance, we might prematurely use up computers that are needed by customers with higher required performance.
For example, consider the following computers and customers:
- Computers: performance \(10\), price \(100\) yen; performance \(5\), price \(50\) yen
- Customers’ required performance: \(5, 10\)
If we sell the most expensive computer (performance \(10\)) to the customer with required performance \(5\), we can no longer sell any computer to the customer with required performance \(10\). On the other hand, if we process the customer with required performance \(10\) first, we can sell to both customers.
Therefore, we process the customers in descending order of required performance. Then, any computer that can be sold to the current customer can also be sold to any subsequent customer.
Why choosing the most expensive available computer is optimal
Let \(x\) be the most expensive unsold computer that can be sold to the current customer.
Fixing the assignments made so far, consider an assignment that maximizes the revenue from all remaining customers. Suppose this assignment sells computer \(y\) to the current customer; then \(B_x \ge B_y\).
- If \(x\) is not sold to anyone:
Changing the computer sold to the current customer from \(y\) to \(x\) still satisfies the condition, and the revenue does not decrease. - If \(x\) is sold to a later customer:
Swap them so that \(x\) is sold to the current customer and \(y\) is sold to that later customer. Since the later customer’s required performance is less than or equal to the current customer’s, \(y\) also satisfies the requirement. The set of sold computers remains unchanged, so the total revenue does not change.
Therefore, if there exists a valid assignment that sells to all customers, choosing the most expensive candidate for the current customer still allows an optimal assignment to be achieved. Repeating this process yields the maximum revenue.
Efficiently finding the most expensive candidate
Checking all computers for each customer would take \(O(NM)\) time. This is too slow for \(N, M \le 10^5\).
Notice that as processing proceeds, the customers’ required performance decreases, meaning the range of sellable computers only expands.
Taking advantage of this property, we can manage the computers as follows:
- Sort the computers in descending order of performance as well.
- Add computers that satisfy the current required performance one by one, starting from those not yet added.
- Maintain the prices of available candidates using a max-heap (priority queue).
Using a max-heap, we can efficiently extract the highest price among the candidates.
Algorithm
- If \(M > N\), output \(-1\) since 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 max-heap
prices, a pointer for scanning computerspos = 0, and the total revenueanswer = 0. - For each customer, let their required performance be
requiredand do the following:- While the
pos-th computer satisfies the performance requirement, push its price into the heap and advancepos. - If the heap is empty, there is no unsold computer that can be sold to the current customer. Output \(-1\) and terminate.
- Add the maximum value in the heap to
answerand remove that element from the heap.
- While the
- After processing all customers, output
answer.
When processing each customer, the heap contains the prices of all unsold computers that can be sold to that customer. Computers added during previous customers’ turns also satisfy the current customer’s requirement, so they can still be used as candidates.
Furthermore, because this greedy choice preserves the possibility of selling to all customers, if the heap becomes empty at any point, it is impossible to sell to all customers in the original problem as well.
Complexity
- Time complexity: \(O(N \log N + M \log M)\)
- Space complexity: \(O(N + M)\)
Sorting takes \(O(N \log N + M \log M)\) time. Each computer is added to the heap at most \(1\) time, and an extraction occurs \(1\) time per customer. If \(M > N\), the algorithm terminates early, so the total time spent on heap operations is bounded by \(O(N \log N)\).
Implementation Notes
Use
long longfor the total revenue.
The total can reach up to \(10^5 \times 10^9 = 10^{14}\) yen, which overflows a 32-bit integer.The performance requirement is “greater than or equal to”.
The condition to add to the heap should becomputers[pos].first >= required.C++’s
priority_queue<int>is a max-heap.
You can get the maximum price withtop()and remove the sold computer from the candidates withpop().Do not reset
pos.
By sorting both computers and customers in descending order, each computer needs to be added to the heap at most once.Computers with the same price are managed as separate elements.
Since this problem only asks for the maximum total revenue, it is sufficient to store only the prices in the heap rather than computer IDs.Source Code
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
vector<pair<int, int>> computers(N);
for (auto& [a, b] : computers) {
cin >> a >> b;
}
vector<int> customers(M);
for (int& c : customers) {
cin >> c;
}
if (M > N) {
cout << -1 << '\n';
return 0;
}
sort(computers.begin(), computers.end(), greater<pair<int, int>>());
sort(customers.begin(), customers.end(), greater<int>());
priority_queue<int> prices;
long long answer = 0;
int pos = 0;
for (int required : customers) {
while (pos < N && computers[pos].first >= required) {
prices.push(computers[pos].second);
++pos;
}
if (prices.empty()) {
cout << -1 << '\n';
return 0;
}
answer += prices.top();
prices.pop();
}
cout << answer << '\n';
return 0;
}
This editorial was generated by gpt-6-astra-medium.
posted:
last update: