Problem Summary
You have N cars and M power outlets.
Car i has capacity A[i] Watt-hours (max it can store).
Outlet j has power B[j] Watts.
There are H hours available.
Rules:
Each outlet can be assigned to at most one car.
Each car can be charged by at most one outlet.
A used outlet charges its car for H hours.
Energy given by outlet j: B[j] * H Watt-hours.
Energy actually stored in car i if using outlet j:
min(A[i], B[j] * H) (cannot exceed car’s capacity).
Goal (per test case): Assign outlets to cars to maximize the sum of stored energy over all cars.
Examples Explanation
Sample:
Input:
3
1 2 2
100
20 40
2 1 2
10 20
11
3 2 1
30 30 30
40 20
Output:
80
20
50
Test case 1:
1 car with capacity 100.
2 outlets: 20 W and 40 W.
H = 2 hours. Possible energies:
Using 20 W: min(100, 20*2) = min(100, 40) = 40
Using 40 W: min(100, 40*2) = min(100, 80) = 80 Best: choose 40 W outlet → total = 80.
Test case 2
2 cars with capacities [10, 20].
1 outlet: 11 W.
H = 2 → energy from outlet = 22 Wh. Best strategy: assign outlet to car with capacity 20:
Car 1: min(10, 22) = 10
Car 2: min(20, 22) = 20 (better) So answer = 20.
Test case 3
3 cars, capacities [30, 30, 30].
2 outlets: [40, 20], H = 1. Energies per outlet: [40, 20]. If we pair optimally:
Car 1 with 40 W: stores min(30, 40) = 30
Car 2 with 20 W: stores min(30, 20) = 20 Total = 50 (Car 3 unused).
Approach
Pattern:
This is a greedy + sorting + matching problem (like “assign resources to maximize total capped benefit”).
Naive Idea:
Check all matchings between cars and outlets:
There are up to min(N, M) assignments.
Naively trying combinations is exponential in worst case, completely infeasible.
Even O(N*M) trying each outlet for each car is too slow when summed over test cases (105 * 105).
Optimal Greedy Approach:
Core observation:
For any car-outlet pair (i, j), benefit is min(A[i], B[j] * H).
Let P[j] = B[j] * H (energy that outlet j can potentially deliver).
Then we want to match cars capacities A with outlet energies P.
Intuition:
Both cars and outlets have capacities or limits.
Classic greedy: sort both sequences and match largest to largest.
Why?
Consider the largest car capacity and largest outlet energy:
If we give the largest outlet to a small-capacity car, we may waste potential energy.
Instead, we should always give stronger outlets to cars that can use more energy.
Concrete strategy:
Compute P[j] = B[j] * H for each outlet.
Sort A (car capacities) in non-increasing order.
Sort P (outlet energies) in non-increasing order.
Traverse both arrays with two pointers:
i over cars (0..N-1), j over outlets (0..M-1).
While i < N and j < M:
Assign car i to outlet j.
Contribution: min(A[i], P[j]).
Add to answer; increment both i++, j++.
Stop when we run out of cars or outlets.
This effectively pairs the k-th biggest car with the k-th biggest outlet among those we use, which is optimal for sum of min() terms.
We do not need to skip any car or outlet in between since all are non-negative and sorted.
Alternative equivalent form:
You could also sort in ascending order and traverse from the end; the logic is the same.
Pseudo-code:
Complexity Analysis:
Let total cars over all test cases be Ntot, total outlets be Mtot.
Per test case:
Computing P: O(M)
Sorting A: O(NlogN)
Sorting P: O(MlogM)
One linear pass: O(N+M)
Using constraints that sums of N and M over all test cases are ≤ 105:
Total Time Complexity:
O(NtotlogNtot + MtotlogMtot) which is fine.
Space Complexity:
O(N+M) for storing arrays and outlet energy array.
Use 64-bit integers (long long in C++/C, long in Java) for totals and B[j] * H.
Java code
JavaScript code
Comments
Post a Comment