PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: justfun21
Testers: iceknight1093, mexomerf
Editorialist: iceknight1093
DIFFICULTY:
1438
PREREQUISITES:
Sorting
PROBLEM:
A restaurant has N dishes; the i-th of which has category A_i and takes B_i time to be cooked.
Find the minimum possible time needed to get at least K distinct categories of food.
EXPLANATION:
If there are less than K distinct categories the answer is -1.
This can be checked in several different ways, for example:
- Put all the A_i values into a set and check its size; or
- Sort the A_i values and count the number of indices such that A_i \leq A_{i+1}.
Now let’s deal with the case when there are \geq K distinct values.
Choosing two different dishes with the same category is clearly not optimal.
This means we choose at most one dish from each category.
For the least total time, from each category we obviously keep only the one that takes the least time to cook.
This can be computed using an array C of length 10^5, initially C_i = \infty for each 1 \leq i \leq 10^5.
Then, for each 1 \leq i \leq N, set C_{A_i} = \min(C_{A_i}, B_i).
Now, C_x contains the minimum time to cook a dish of category x.
The answer is then the sum of the K smallest values of C, which can be found by sorting C.
Instead of an array of size 10^5, you can also use a map (std::map
in C++, HashMap/TreeMap
in Java, dict
in Python) to represent C.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Setter's code (C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
// setIO("input");
ios_base::sync_with_stdio(false);
cin.tie();cout.tie();
long long TT = 1;
long long suma = 0;
cin>>TT;
for(long long TR = 1;TR <= TT;TR++){
long long n,k;
cin>>n>>k;
suma+=n;
assert(n>=1 and n<=100000);
assert(k>=1 and k<=100000);
vector<long long>a(n),b(n);
for(long long i=0;i<n;i++){
cin>>a[i];
assert(a[i]>=1 and a[i]<=100000);
}
for(long long i=0;i<n;i++){
cin>>b[i];
assert(b[i]>=0 and b[i]<=100000);
}
map<long long,long long>mp;
for(long long i=0;i<n;i++){
mp[a[i]] = 10000007;
}
for(long long i=0;i<n;i++){
mp[a[i]] = min(mp[a[i]],b[i]);
}
vector<long long>time;
for(auto it:mp){
if(it.second!=10000007){
time.push_back(it.second);
}
}
sort(time.begin(),time.end());
if(time.size()<k){
cout<<-1<<"\n";
continue;
}
long long ans = 0;
for(long long i=0;i<k;i++){
ans+=time[i];
}
cout<<ans<<"\n";
}
assert(suma>=1 and suma<=100000);
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
int a[n], b[n];
map<int, int> mpp;
for (int i = 0; i < n; i++){
cin >> a[i];
}
for (int i = 0; i < n; i++){
cin >> b[i];
}
for (int i = 0; i < n; i++){
if(mpp.find(a[i]) == mpp.end()){
mpp[a[i]] = b[i];
}else{
mpp[a[i]] = min(mpp[a[i]], b[i]);
}
}
vector<int> v;
for(auto &it: mpp){
v.push_back(it.second);
}
sort(v.begin(), v.end());
int sum = -1;
if(v.size() >= k){
sum = 0;
for (int i = 0; i < k; i++){
sum += v[i];
}
}
cout << sum << "\n";
}
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
least = [10**12 for i in range(10**5 + 5)]
for i in range(n): least[a[i]] = min(least[a[i]], b[i])
ans = sum(sorted(least)[0:k])
print(ans if ans < 10**12 else -1)