Distinct Element Sum with Minimum Cost
You are given a list of N integers. You want to reduce the number of distinct elements in the list to at most K. You can perform an operation: remove an element from the list. The cost of removing an element is its value. Find the minimum total cost to achieve the goal.
Input
The first line contains two integers N and K. The second line contains N integers: a_1, a_2, ..., a_n.
Output
Print a single integer: the minimum total cost.
Constraints
1 <= K <= N <= 200000 1 <= a_i <= 10^9
Example 1
7 3 1 1 2 3 3 3 5
2
Distinct elements are {1:2, 2:1, 3:3, 5:1}. We have 4 distinct elements and need to reduce to 3. Remove the element with the smallest value (1) at cost 1*2=2. Remaining distinct elements: {2:1, 3:3, 5:1}. Total cost: 2.
Example 2
5 2 10 20 10 30 20
20
Distinct elements are {10:2, 20:2, 30:1}. We have 3 distinct elements and need to reduce to 2. Remove the element with the smallest value (10) at cost 10*2=20. Remaining distinct elements: {20:2, 30:1}. Total cost: 20.
Hints
Similar problems
- Distinct Elements with Minimum Total CostMedium
- Process Tasks by DeadlineMedium
- Distinct Elements CountMedium
- Maximize Distinct Elements After OperationsMedium
- Minimize Maximum Difference of Elements in IntervalsHard
- Find K Distinct Element FrequenciesMedium
More topics: Hash Map and Hashing problems, Greedy problems, Heap and Priority Queue problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
7 3 1 1 2 3 3 3 5
5 2 10 20 10 30 20