Making Mexes
실버 I의견: 0
You are given an array \(a\) of \(N\) non-negative integers \(a_1, a_2, \dots, a_N\)
(\(1\le N\le 2\cdot 10^5, 0\le a_i\le N\)). In one operation, you can change any
element of \(a\) to any non-negative integer.
The mex of an array is the minimum non-negative integer that it does not
contain. For each \(i\) in the range \(0\) to \(N\) inclusive, compute the minimum
number of operations you need in order to make the mex of \(a\) equal \(i\).
Problem credits: Benjamin Qi
SCORING
- Inputs 2-6: \(N\le 10^3\)
- Inputs 7-11: No additional constraints.
Problem credits: Benjamin Qi
The first line contains \(N\).
The next line contains \(a_1,a_2,\dots, a_N\).
For each \(i\) in the range \(0\) to \(N\), output the minimum number of operations
for \(i\) on a new line. Note that it is always possible to make the mex of \(a\)
equal to any \(i\) in the range \(0\) to \(N\).
4
2 2 2 01
0
3
1
2- To make the mex of \(a\) equal to \(0\), we can change \(a_4\) to \(3\) (or any positive integer). In the resulting array, \([2, 2, 2, 3]\), \(0\) is the smallest non-negative integer that the array does not contain, so \(0\) is the mex of the array.
- To make the mex of \(a\) equal to \(1\), we don't need to make any changes since \(1\) is already the smallest non-negative integer that \(a = [2, 2, 2, 0]\) does not contain.
- To make the mex of \(a\) equal to \(2\), we need to change the first three elements of \(a\). For example, we can change \(a\) to be \([3, 1, 1, 0]\).
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > February > Bronze
평가 및 의견
Making Mexes
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Making Mexes