D - パソコンの販売 / Selling Computers 解説 by admin 印刷ページ
Gemini 3.8 Flash (High)Overview
In this problem, we are asked to allocate one PC to each of \(M\) customers from a set of \(N\) PCs such that the conditions are satisfied, while maximizing the total sales revenue.
By sorting the customers in ascending order of their required performance, this problem can be reduced to the “Job Scheduling with Deadlines” problem. By combining a greedy approach that processes PCs in descending order of price with a Union-Find data structure to quickly find available slots, we can solve the problem in \(O(N \log N + M \log M)\) time.
Analysis
1. Clarifying Conditions and the Trivial Case
A PC \(i\) can be sold to customer \(j\) if and only if \(A_i \ge C_j\). Furthermore, since we must allocate a distinct PC to each customer, if the number of PCs is less than the number of customers (\(N < M\)), it is strictly impossible to sell to everyone (in this case, we can immediately output -1).
2. Sorting Customers and the “Range of Satisfiable Customers”
Let us sort the customers’ required performances \(C\) in ascending order: $\(C_1 \le C_2 \le \dots \le C_M\)$
With this ordering, when a PC has performance \(A_i\), the customers who can purchase this PC are those satisfying \(C_j \le A_i\). Since \(C\) is sorted in ascending order, if we let \(r_i\) be the maximum customer index satisfying \(A_i \ge C_j\), this PC can be sold to any of the customers \(1, 2, \dots, r_i\), and cannot be sold to customer \(r_i + 1\) or any customer after that.
This value \(r_i\) can be found efficiently in \(O(\log M)\) using binary search (upper_bound) on the sorted array \(C\).
3. Reduction to the Job Scheduling Problem
This problem can be rephrased as the following “Job Scheduling with Deadlines” problem: - Regard customers \(1, 2, \dots, M\) as “slots at time \(1, 2, \dots, M\)”. - Regard PC \(i\) as a “job with deadline \(r_i\) and profit \(B_i\)”. - At most one job can be assigned to each slot. - Maximize the total profit and determine whether all \(M\) slots can be filled.
4. Greedy Approach
To maximize profit (sales revenue), it is intuitive to prioritize choosing PCs with higher prices \(B_i\), and this is also guaranteed to be optimal by matroid theory.
Now, to which customer should we assign a chosen PC \(i\) (which can satisfy customers \(1 \dots r_i\))? In conclusion, it is best to assign it to the customer with the largest index among available customers \(\le r_i\) (the latest available slot). This is because leaving slots for customers with smaller indices (customers with lower required performance) empty leaves more opportunities to assign “PCs with lower performance and smaller \(r\)” that are processed later.
5. Speeding Up (Using Union-Find)
If we use linear search to find “the largest available index \(\le r_i\)” for each PC, it will take \(O(NM)\) time in the worst case, resulting in TLE (Time Limit Exceeded).
Therefore, we use a Union-Find (disjoint-set data structure) to manage the available indices.
- Prepare a Union-Find managing slots \(0\) to \(M\), where initially the representative of element \(x\) is \(x\) itself (indicating that \(x\) is available).
- When slot \(k\) is used, merge the representative of \(k\) into the group of \(k - 1\).
- With this, simply calling find(r) yields the largest currently available index \(\le r\) in amortized \(O(\alpha(M))\) time (almost constant time). If it returns \(0\), it means that there is no available slot that can be assigned.
Algorithm
- If \(N < M\), output
-1and terminate. - Sort the array \(C\) of customers’ required performance in ascending order.
- For each PC \(i\), use binary search (
std::upper_bound) to find the number of customers \(r_i\) satisfying \(A_i \ge C_j\). - Sort the list of PCs in descending order of price \(B_i\).
- Initialize a Union-Find of size \(M + 1\), and for each PC in descending order of price, do the following:
- Find the largest available slot \(s = \text{find}(r_i)\) that is \(\le r_i\).
- If \(s > 0\), sell the PC to that customer:
- Add \(B_i\) to the total sales revenue.
- Increment the count of sold PCs by \(1\).
- Merge slot \(s\) into \(s - 1\) (
parent[s] = find(s - 1)).
- If \(s = 0\), skip this PC because there is no available customer who can purchase it.
- If the number of sold PCs is finally exactly \(M\), output the total sales revenue; otherwise, since we could not sell to all customers, output
-1.
Complexity
- Time Complexity: \(O(N \log N + M \log M)\)
- Sorting the array of customers \(C\): \(O(M \log M)\)
- Binary search for \(r_i\) for each PC: \(O(N \log M)\)
- Sorting the PCs: \(O(N \log N)\)
- Greedy assignment process: \(O(N \alpha(M))\) for \(N\) Union-Find operations
- Overall, it is \(O(N \log N + M \log M)\), which runs well within the time limit for the constraints \(N, M \le 10^5\).
- Space Complexity: \(O(N + M)\)
- \(O(N + M)\) memory is used to store the PC information, the customer required performance array, and the Union-Find array.
Implementation Notes
Using Slot \(0\) as a Sentinel:
- Treat customer indices as 1-indexed (\(1 \dots M\)), and use index \(0\) as a sentinel representing “unassignable”. If
find(r)returns \(0\), we can easily determine that no available slot exists.
- Treat customer indices as 1-indexed (\(1 \dots M\)), and use index \(0\) as a sentinel representing “unassignable”. If
Preventing Overflow:
The total sales revenue can reach up to \(M \times \max(B_i) = 10^5 \times 10^9 = 10^{14}\), which exceeds the upper bound of a 32-bit integer (approximately \(2 \times 10^9\)). Make sure to use a 64-bit integer type (such as
long longin C++) for the variable that stores the total revenue.Source Code
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
struct Laptop {
long long a;
long long b;
};
struct Item {
int r;
long long b;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
if (!(cin >> n >> m)) return 0;
vector<Laptop> laptops(n);
for (int i = 0; i < n; ++i) {
cin >> laptops[i].a >> laptops[i].b;
}
vector<long long> c(m);
for (int j = 0; j < m; ++j) {
cin >> c[j];
}
if (n < m) {
cout << -1 << "\n";
return 0;
}
sort(c.begin(), c.end());
vector<Item> items(n);
for (int i = 0; i < n; ++i) {
auto it = upper_bound(c.begin(), c.end(), laptops[i].a);
items[i].r = distance(c.begin(), it);
items[i].b = laptops[i].b;
}
sort(items.begin(), items.end(), [](const Item& x, const Item& y) {
return x.b > y.b;
});
vector<int> parent(m + 1);
iota(parent.begin(), parent.end(), 0);
auto find = [&](auto self, int x) -> int {
return parent[x] == x ? x : parent[x] = self(self, parent[x]);
};
int count = 0;
long long total_revenue = 0;
for (const auto& item : items) {
if (item.r == 0) continue;
int slot = find(find, item.r);
if (slot > 0) {
total_revenue += item.b;
count++;
parent[slot] = find(find, slot - 1);
}
}
if (count == m) {
cout << total_revenue << "\n";
} else {
cout << -1 << "\n";
}
return 0;
}
This editorial was generated by gemini-3.8-flash-high.
投稿日時:
最終更新: