PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: yash_daga
Tester: satyam_343
Editorialist: iceknight1093
DIFFICULTY:
1479
PREREQUISITES:
Sorting
PROBLEM:
You have N cars and M power outlets.
The i-th car has energy capacity A_i Watt-hour.
The i-th output provides B_i Watt power.
If you have H hours, what’s the maximum total power that can be charged?
Each car can use at most one charger, each charger can charge at most one car.
EXPLANATION:
Let K = \min(N, M).
Certainly, we can only use at most K outlets, and charge at most K cars.
Since only K outlets can be used, it makes sense to take the best K of them, i.e, the K highest B_i values.
Similarly, it makes sense to take the cars with most capacity - the K largest A_i values.
These can be found by sorting the array in descending order.
Now, let
We’d like to match each outlet to a car.
It’s not hard to see that it’s best to match the best outlet to the highest-capacity car, the second best outlet to the second highest-capacity car, and so on.
That is, it’s optimal to match A_i with B_i for each 1 \leq i \leq K. A proof can be found below.
Matching A_i with B_i gives us a total of \min(A_i, H\cdot B_i) energy.
So, after sorting as above, the answer is simply
Proof of the greedy choice
Suppose A_1 is not matched with B_1.
Let A_1 be matched with B_j, and B_1 be matched with A_i.
Here, i, j \gt 1.
Consider what happens if we match A_1 with B_1 and A_i with B_j instead.
- Initially, A_1 was matched with B_j and B_1 with A_i.
This provided a total of \min(A_1, H\cdot B_j) + \min(A_j, H\cdot B_1) power. - After swapping, they’ll instead provide \min(A_1, H\cdot B_1) + \min(A_i, H\cdot B_j) power.
- A bit of case analysis should tell you that the second expression is certainly not worse than the first; and is sometimes even larger.
This means it’s optimal to match A_1 with B_1.
Once this is done, continue the argument with i = 2, 3, 4, \ldots, K to fix everything.
TIME COMPLEXITY
\mathcal{O}(N\log N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
int32_t main()
{
int t;
cin>>t;
while(t--)
{
int n, m, h;
cin>>n>>m>>h;
vector <int> a(n), b(m);
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<m;i++)
cin>>b[i];
sort(a.begin(), a.end(), greater <int> ());
sort(b.begin(), b.end(), greater <int> ());
long long sum=0;
for(int i=0;i<min(n, m);i++)
sum+=min(1ll*a[i], 1ll*b[i]*h);
cout<<sum<<"\n";
}
}
Editorialist's code (Python)
for _ in range(int(input())):
n, m, h = map(int, input().split())
a = sorted(list(map(int, input().split())))[::-1]
b = sorted(list(map(int, input().split())))[::-1]
ans = 0
for i in range(min(n, m)):
ans += min(a[i], h*b[i])
print(ans)