Maximize Distinct Elements After Operations
You are given a multiset of N integers. You can perform an operation: choose any element x from the multiset and replace it with x-1. This operation can be performed any number of times. Your goal is to maximize the number of distinct elements in the multiset after performing some operations. Each element x must remain positive after all operations. If there are multiple ways to achieve the maximum number of distinct elements, choose the one that results in the smallest sum of all elements in the multiset.
Input
First line: an integer N. Second line: N space-separated integers, the elements of the multiset.
Output
A single integer: the maximum number of distinct elements achievable.
Constraints
1 <= N <= 200000. 1 <= elements[i] <= 10^9.
Example 1
5 2 2 3 4 5
4
Initially we have {2, 2, 3, 4, 5}. Sorted: [2, 2, 3, 4, 5]. Heap: [2]. Process second 2: 2 <= heap.top(2). Try 2-1=1. 1>0 and 1!=2. Replace 2 with 1. Heap: [1]. Process 3: 3 > heap.top(1). Push 3. Heap: [1, 3]. Process 4: 4 > heap.top(1). Push 4. Heap: [1, 3, 4]. Process 5: 5 > heap.top(1). Push 5.
Example 2
4 1 1 1 1
1
Sorted: [1, 1, 1, 1]. Heap: [1]. Process second 1: 1 <= heap.top(1). Try 1-1=0. 0 is not >0. Discard. Heap: [1]. Process third 1: discard. Heap: [1]. Process fourth 1: discard. Heap: [1]. Final size: 1. Distinct element {1}.
Hints
Similar problems
- Distinct Element Sum with Minimum CostMedium
- Process Tasks by DeadlineMedium
- Distinct Elements with Minimum Total CostMedium
- Minimize Maximum Difference of Elements in IntervalsHard
- Maximize Non-overlapping IntervalsMedium
- Maximum Sum of Non-Overlapping SegmentsMedium
More topics: 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()
5 2 2 3 4 5
4 1 1 1 1