公式

D - パソコンの販売 / Selling Computers 解説 by admin 印刷ページ

Claude Opus 5 (High)

Overview

Each customer will buy any computer as long as its performance is at least \(C_j\). This problem asks us to find an assignment (matching) between customers and computers that maximizes the total revenue (the sum of the prices). It can be solved using a greedy approach combined with a priority queue (max-heap), where we process customers in descending order of required performance and assign each the most expensive computer they can purchase.

Analysis

Observation 1: Prices are Independent of Constraints

The set of computers that customer \(j\) can purchase is \(\{i : A_i \ge C_j\}\), and the price \(B_i\) has no influence on whether a computer can be bought. Thus, to maximize total revenue, we only need to assign the most expensive computers possible while satisfying the performance requirements.

Observation 2: The Sets of Eligible Computers are Nested

If \(C_j \ge C_k\), the set of computers that customer \(j\) can purchase is completely contained within the set of computers that customer \(k\) can purchase:

\[C_j \ge C_k \implies \{i : A_i \ge C_j\} \subseteq \{i : A_i \ge C_k\}\]

In other words, there is a clear nested structure: “the stricter the requirement, the fewer options the customer has.” In this scenario, it is natural to process customers with stricter requirements (larger \(C_j\)) first. If we postpone customers with fewer choices, the computers they could have bought might be taken by other customers.

Observation 3: We Can Assign the Most Expensive Computer to the Strictest Customer

For the customer \(j\) with the strictest requirement, it is optimal to assign the most expensive computer \(y\) among those that satisfy the condition.

Proof (exchange argument): Suppose that in some optimal solution, customer \(j\) receives computer \(x\) (where \(B_x \le B_y\)). - If \(y\) is not sold to any customer: Replacing \(x\) with \(y\) is valid since \(A_y \ge C_j\), and the total revenue does not decrease. - If \(y\) is sold to another customer \(k\): Since \(j\) is the customer with the strictest requirement, we have \(C_k \le C_j \le A_x\). Thus, swapping \(x\) and \(y\) satisfies the conditions for both customers, and the total revenue remains unchanged.

In either case, we can construct an optimal solution where customer \(j\) receives the most expensive computer, which justifies the greedy strategy. From there, we can handle the remaining smaller subproblem without \(j\) and \(y\) using the same argument.

What Happens with a Naive Implementation?

If we perform a linear search for each customer to find the unused computer with the maximum \(B_i\) among those satisfying \(A_i \ge C_j\), it takes \(O(NM)\) time. With \(N, M \le 10^5\), this requires around \(10^{10}\) operations and will result in TLE.

To resolve this, we maintain the set of candidate computers using a priority queue (max-heap). As we process the customers in descending order of \(C_j\), the value of \(C_j\) monotonically decreases, meaning computers are only ever “added” to the candidate set and never “removed” (by the nested structure in Observation 2). Therefore, if we sort the computers in descending order of \(A_i\), we can manage the candidate set like a two-pointer technique by pushing each computer into the heap at most once.

Algorithm

  1. Sort the computers in descending order of \(A_i\).
  2. Sort the customers’ requirements \(C_j\) in descending order.
  3. Initialize an empty max-heap (priority_queue<int>, keyed by price \(B\)) and set the computer pointer idx = 0.
  4. Iterate through the customers \(j = 1, 2, \dots, M\) (in descending order of \(C\)):
    • While the computer at idx has performance at least \(C_j\), push its price into the heap and increment idx (all computers that the current customer can buy are now in the heap).
    • If the heap is empty, there are no computers left that can be sold to this customer, so output -1 and terminate.
    • Pop the maximum value from the heap and add it to the total revenue.
  5. If all customers have been served, output the total revenue.

Example

Consider \(N = 3\), computers \((A, B) = (10, 5), (7, 100), (3, 50)\), and customers \(C = (3, 7)\).

After sorting in descending order, the computers are \((10, 5), (7, 100), (3, 50)\), and the customers are \(C = 7, 3\).

  • Customer \(C = 7\): Push computers \((10, 5), (7, 100)\) with \(A \ge 7\) into the heap \(\to\) heap \(\{5, 100\}\). Sell the most expensive computer, \(100\). Revenue: \(100\).
  • Customer \(C = 3\): Add \((3, 50)\) to the heap \(\to\) heap \(\{5, 50\}\). Sell the most expensive computer, \(50\). Total revenue: \(150\).

The answer is \(150\). We can see that if we had started from the customer with the least strict requirement or assigned cheaper computers first, we would not achieve the maximum revenue.

Regarding the Condition for Outputting “-1”

When \(M > N\) or when there are not enough computers to satisfy the requirements, the heap will inevitably become empty at some point during the procedure above. Because we process customers in descending order of strictness, the situation where “(the number of computers that could have been used) \(< k\)” after attempting to process the top \(k\) customers occurs if and only if no valid matching exists (the set of the \(k\) strictest customers serves as a violating subset in Hall’s Marriage Theorem). Therefore, we can safely terminate and output -1 as soon as the heap becomes empty.

Complexity

  • Time Complexity: \(O((N + M) \log N)\) (sorting and heap operations; each computer is pushed/popped at most once)
  • Space Complexity: \(O(N + M)\)

Implementation Details

  • Beware of integer overflow for total revenue: Since \(M \le 10^5\) and \(B_i \le 10^9\), the sum can reach around \(10^{14}\). Use a 64-bit integer type like long long (in languages other than Python).

  • Keep idx outside the loop: Do not reset it to 0 for each customer. It advances at most \(N\) times in total across the entire process, which is the key to keeping the time complexity bounded by \(O(N \log N)\).

  • It is sufficient to store only the “price \(B\)” in the heap (there is no need to keep track of which specific computer it corresponds to).

  • Make sure to sort both: “computers in descending order of \(A\)” and “customers in descending order of \(C\)”. Do not forget to sort in descending order (e.g., using greater<int>() or a lambda expression).

  • Since the input and output can be up to around \(2 \times 10^5\) lines, in C++ it is safer to use scanf or disable stream synchronization (ios::sync_with_stdio(false)).

    Source Code

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, M;
    if(scanf("%d %d", &N, &M)!=2) return 0;
    vector<pair<int,int>> pc(N);
    for(int i=0;i<N;i++){
        int a,b; scanf("%d %d",&a,&b);
        pc[i]={a,b};
    }
    vector<int> C(M);
    for(int j=0;j<M;j++) scanf("%d",&C[j]);
    sort(pc.begin(), pc.end(), [](const pair<int,int>&x, const pair<int,int>&y){
        return x.first > y.first;
    });
    sort(C.begin(), C.end(), greater<int>());
    priority_queue<int> pq;
    int idx = 0;
    long long total = 0;
    for(int j=0;j<M;j++){
        while(idx < N && pc[idx].first >= C[j]){
            pq.push(pc[idx].second);
            idx++;
        }
        if(pq.empty()){
            printf("-1\n");
            return 0;
        }
        total += pq.top();
        pq.pop();
    }
    printf("%lld\n", total);
    return 0;
}

This editorial was generated by claude5opus-high.

投稿日時:
最終更新: