codeforces rating 800 수준의 쉬운 문제를 풀게 해 보았습니다.
Okay, let's try to figure out how to solve this problem. So, the task is to find the minimum number of elements to delete from an array so that the resulting array is balanced. A balanced array means that every integer x that appears in the array occurs exactly x times.
First, I need to understand what makes an array balanced. For example, if the number 2 is present, it should appear exactly 2 times. If 4 is present, it should appear exactly 4 times. But if a number like 3 is present, it needs to be exactly 3 times. However, if a number like 5 is present but the array length is only 10, maybe it's impossible to have 5 occurrences, but according to the problem statement, the array after deletion must satisfy this condition for all numbers present.
Wait, but the problem says "every integer x that occurs at least once, occurs exactly x times". So, for any x that is present in the array, the count of x must be equal to x. So, if x is 0, but the problem states that a_i can be 0. Wait, the input says 0 ≤ a_i ≤ n. Hmm, but if x is 0, then the count should be exactly 0. But if 0 is present, then the count of 0 must be 0, which is a contradiction. Wait, that can't be. Wait, maybe x has to be a positive integer? Let me check the problem statement again.
The problem says "every integer x that occurs at least once, occurs exactly x times". So, if x is 0, then for the array to be balanced, 0 must occur exactly 0 times. But if 0 is present, that's a problem. So, any array containing 0 cannot be balanced unless 0 is not present. Wait, but according to the input constraints, a_i can be 0. So, in the example input, there's a test case with 0. Let's check the example.
Looking at the example input:
The fourth test case is:
1 0
Wait, the input example shows:
input:
4
3
1 2 2
5
1 1 2 2 3
10
1 2 3 2 4 4 4 4 5 2
1
0
Wait, the last test case is n=1, and the array is [0]. The output is 1. Because to make it balanced, since 0 is present, but according to the definition, it should occur exactly 0 times. So, you have to delete the 0. Hence, output is 1.
So, for x=0, the condition is that if 0 is present, then it must occur exactly 0 times, which is impossible. Therefore, any occurrence of 0 must be deleted. So, in the array, all 0s must be removed because they can't satisfy the condition. Because if you have a 0 in the array, then x=0 must occur exactly 0 times, which is a contradiction. Therefore, all 0s have to be deleted.
So, the first step is to note that any 0s in the array must be removed. Because they can't be part of a balanced array. Because for x=0, the count should be 0, but if it's present, count is at least 1. So, 0s are invalid and must be deleted.
Now, for other numbers (x ≥ 1), we need to decide whether to keep them or not. For each x, if we decide to keep it, then the count of x must be exactly x. Otherwise, we have to delete all occurrences of x.
Wait, but maybe for some x, it's better to delete some occurrences so that the count becomes x. For example, if x is 2 and there are 3 occurrences of 2, then we can delete 1 occurrence to make it 2, which is valid. But if there are 4 occurrences of 2, then to make it balanced, we need exactly 2 occurrences, so we delete 2. However, if the count is less than x, like x=3 and count=2, then we can't have 3 in the array because it would require exactly 3 occurrences, but we only have 2. So, in that case, we must delete all occurrences of 3 (since having 3 in the array would require it to have exactly 3 occurrences, which we don't have).
Wait, but maybe for some x, the count is more than x, so we can delete (count - x) elements. But if the count is less than x, then we can't have x in the array, so we have to delete all of them.
Wait, let's formalize this.
For each number x (x ≥ 1):
-
Let c be the count of x in the array.
-
If c < x: then we cannot have x in the balanced array, because to have x present, it needs to have exactly x occurrences, but we only have c. So, all c occurrences must be deleted.
-
If c ≥ x: then we can choose to keep x in the array by deleting (c - x) elements. However, we might also choose to delete all c elements (if it's better for the total deletions). Wait, but why would we choose to delete all? Because maybe keeping x would require deleting (c - x) elements, but if x is not kept, we delete c elements. So, for each x, the minimal deletions for that x is min(c, c - x) if c >=x? Wait no.
Wait, for x where c >=x: the options are:
Either:
- Keep x: then we need to delete (c - x) elements (so that the count becomes x).
OR
- Don't keep x: delete all c elements.
So, for each x, the minimal deletions for that x is min(c - x, c) but only if c >=x. Wait, but c - x is less than c when x>0. Because c -x < c since x is positive. So, for c >=x, it's better to keep x (since deleting (c -x) is less than deleting c). However, there's a catch: but if we keep x, we have to make sure that x is part of the balanced array. However, the problem is that when we decide to keep multiple x's, their counts must all satisfy the condition.
Wait, but the balanced condition requires that for every x present, count(x) = x. So, when we decide which x's to keep, we need to select a subset S of the numbers (excluding 0) such that for each x in S, the count of x in the original array is at least x (so that we can delete down to x), and for the numbers not in S, we delete all their occurrences.
Wait, but for example, suppose we have x=2 with count 3. If we keep x=2, we delete 1 element. But if we have another x=3 with count 3, then keeping both would require that 2 occurs exactly 2 times (so delete 1) and 3 occurs exactly 3 times (so delete 0). But the total deletions would be 1 + 0 = 1. However, maybe there's a case where keeping some x's is better than others.
Wait, but the problem is that for each x, the decision to keep or not is independent? No, because the total deletions is the sum over all x of the deletions for each x.
Wait, no. Because for each x, if we decide to keep it, we delete (c_x - x) elements. If we don't keep it, we delete c_x elements. So, the total deletions would be sum over all x of [ if kept: (c_x -x), else: c_x ].
But the catch is that for the array to be balanced, the set of kept x's must satisfy that for each kept x, c_x >=x (so that (c_x -x) is non-negative). Because if c_x <x, then keeping x is impossible (since we can't have negative deletions), so for those x's, we have to delete all c_x elements.
Wait, but for x where c_x <x, the only option is to delete all c_x elements. For x where c_x >=x, we can choose to either delete (c_x -x) elements (and keep x) or delete all c_x elements (and not keep x). So, for each x with c_x >=x, we have a choice: pay (c_x -x) or pay c_x. Since (c_x -x) < c_x (because x>0), it's better to pay (c_x -x) if possible.
But wait, but there's a problem here. Suppose x=2 and c_x=3. If we keep x=2, then the count becomes 2, which is valid. However, what if another number, say x=1, has c_x=1. Then keeping both would be okay. But if x=1 has c_x=0, then it's not present.
Wait, but the problem is that for the balanced array, all numbers present must satisfy count(x)=x. So, if we keep x=2 (with count 2 after deletion), and there's no other numbers, then it's balanced. But if there are other numbers, like x=3 with count 3, then it's okay.
So, the key is: for each x (x >=1), if we decide to include x in the balanced array, then we need c_x >=x, and we delete (c_x -x) elements. If we don't include x, we delete all c_x elements.
But the problem is that the choice of which x's to include affects the total deletions. For example, suppose x=2 has c_x=3 (so keeping it would cost 1 deletion), and x=3 has c_x=3 (keeping it would cost 0 deletions). If we keep both, total deletions is 1+0=1. But if keeping both is allowed (i.e., the resulting array has 2 occurring 2 times and 3 occurring 3 times), then that's a valid balanced array.
Wait, but in this case, the array after deletion would have two 2's and three 3's. So, for x=2, count is 2 (good), for x=3, count is 3 (good). So, it's balanced.
So, the problem reduces to selecting a subset S of the numbers (x >=1) such that for each x in S, c_x >=x, and the total deletions is sum_{x not in S} c_x + sum_{x in S} (c_x -x). Which can be rewritten as sum_{all x} c_x - sum_{x in S} x.
Because sum_{x not in S} c_x + sum_{x in S} (c_x -x) = sum c_x - sum_{x in S} x.
Since sum c_x is the total number of elements (excluding 0s, but 0s are all deleted, so sum c_x for x >=1 is n minus the number of 0s).
Wait, the total number of elements in the original array is n. The number of 0s is, say, z. So sum_{x >=1} c_x = n - z.
The total deletions would be z (for all 0s) plus [sum_{x >=1} c_x - sum_{x in S} x ].
Wait, because sum_{x not in S} c_x + sum_{x in S} (c_x -x) = sum_{x >=1} c_x - sum_{x in S} x.
So total deletions is z + ( (n - z) - sum_{x in S} x ) ) = n - sum_{x in S} x.
Ah! Because z + (n - z - sum_S x) = n - sum_S x.
So the total number of deletions is n minus the sum of x for all x in S.
Therefore, to minimize the number of deletions, we need to maximize sum_{x in S} x, where S is a subset of the possible x's (x >=1), such that for each x in S, c_x >=x.
Because deletions = n - sum_S x. So maximizing sum_S x minimizes deletions.
Ah, this is a crucial insight. So the problem reduces to selecting a subset S of numbers (x >=1) where for each x in S, the original count c_x is at least x, and the sum of x in S is as large as possible. Then, the minimal deletions is n minus that maximum sum.
Wait, but let's verify with the examples.
Take the first example:
Input: 3 elements [1, 2, 2]
n=3.
The array is [1,2,2].
For x=1: c_x=1. Since 1 >=1, can include x=1. sum +=1.
For x=2: c_x=2. 2 >=2, can include. sum +=2. Total sum is 3.
So deletions = 3 - 3 =0. Which matches the sample output.
Another example: second test case.
Input: 5 elements [1,1,2,2,3]
n=5.
Compute c_x:
x=1: c=2. 2 >=1: can include. If included, contributes 1.
x=2: c=2. 2 >=2: contributes 2.
x=3: c=1. 1 <3: cannot include.
So possible S options:
Option 1: include 1 and 2. sum is 1+2=3. deletions=5-3=2. Which matches the sample output.
Another option: include only 2. sum=2. deletions=5-2=3. Worse.
Include only 1: sum=1. deletions=4. Worse.
So maximum sum is 3, deletions=2.
Yes, this works.
Third example: the third test case.
Input: 10 elements [1,2,3,2,4,4,4,4,5,2]
n=10.
Compute c_x:
x=1: c=1. 1 >=1: yes.
x=2: c=3 (elements 2,2,2). 3 >=2: yes.
x=3: c=1. 1 <3: no.
x=4: c=4. 4 >=4: yes.
x=5: c=1. 1 <5: no.
So possible S:
Check which x's can be included.
x=1: can include (sum +=1)
x=2: can include (sum +=2)
x=4: can include (sum +=4)
Total sum is 1+2+4=7.
deletions=10 -7=3. Which matches the sample output of 3.
Yes.
Fourth example: input is [0], n=1.
z=1 (number of 0s). sum_S x is 0 (since no x >=1 can be included). deletions=1 -0=1. Correct.
Another example: if the array is [2,2,2], n=3.
x=2: c=3. 3 >=2. So can include x=2. sum is 2. deletions=3-2=1. But the problem statement says [2,2,2] is not balanced. So to make it balanced, we need to have exactly 2 occurrences. So delete 1 element. Which matches deletions=1. So the output would be 1.
But according to the problem statement, ([2]) is not balanced (since 2 occurs once, but needs to occur 2 times), and ([2,2,2]) is also not balanced (needs exactly 2, but has 3). So to make it balanced, delete 1 element to get [2,2], which is balanced. So deletions=1. Which is 3-2=1. Correct.
So the approach is:
For each test case:
-
Count the frequency of each number (for x >=0).
-
For x=0: all must be deleted. So the number of 0s is part of the deletions, but according to our formula, deletions = n - sum_S x. Wait, in the formula, sum_S x is sum of x in S (x >=1). The 0s are all deleted, but according to the formula, the deletions is n - sum_S x. Let's check:
Total elements n.
sum_S x is the sum of x for x in S.
But sum_S x is the total number of elements in the balanced array. Because for each x in S, the count is x, so total elements is sum x.
Therefore, the number of elements to keep is sum_S x, so deletions is n - sum_S x.
Yes. Because the balanced array has sum_S x elements, so deletions is n - sum_S x.
So the 0s are part of the n, and since they are not in S (because x=0 can't be in S), they are all deleted as part of the n - sum_S x.
So the formula holds.
Therefore, the problem reduces to: find the maximum possible sum of x's where for each x, the count of x in the array is at least x. Then, the answer is n minus that sum.
So the steps for each test case are:
-
Read n.
-
Read the array.
-
Compute frequency counts for each number (from 0 to n, since a_i is between 0 and n).
-
For x from 1 to n (since x=0 can't be in S):
-
If frequency >=x, then x can be included in S, contributing x to the sum.
-
But wait, no: for each x, even if frequency >=x, we can choose to include it or not. But to maximize the sum, we would include it if possible.
Wait, but for a given x, if frequency >=x, including it adds x to the sum. Not including it adds 0. So to maximize the sum, for each x where frequency >=x, we should include it.
Wait, but is that always the case? Let's think.
Suppose x=2 and frequency =3 (so can include, adding 2 to sum). Also, x=3 and frequency =3 (can include, adding 3). So including both gives sum 5. Which is better than including just one.
Yes, because each x that meets the condition (frequency >=x) contributes x to the sum, so including all such x's would maximize the sum.
Wait, but what if including a larger x prevents including a smaller one? No, because the conditions are independent. For example, x=2 and x=3 can both be included as long as their frequencies are >=2 and >=3 respectively.
Wait, but the frequency counts are independent. For example, the count of 2 is 3 (so 3 >=2), and count of 3 is 3 (3 >=3). So both can be included. The sum would be 2+3=5.
Yes, so there's no conflict between different x's. So the maximum sum is simply the sum of all x where frequency >=x.
Wait, but wait: what if x=2 has frequency 3 (so can include, sum +=2), but x=1 has frequency 0 (so cannot include). Then sum is 2.
But what if x=1 has frequency 1 (so can include, sum +=1), and x=2 has frequency 3 (sum +=2). Then total sum is 3.
So the maximum sum is the sum of all x where frequency >=x.
Wait, but is that correct?
Wait, for example, take x=2 with frequency 3. So including x=2 gives sum +=2.
But what if x=2 has frequency 5. Then including x=2 would add 2 to the sum. But perhaps there's a better way. No, because 2 is the maximum possible contribution for x=2. Because if you include x=2, you get 2. If you don't, you get 0. So including is better.
Yes. So for each x, if frequency >=x, then including x gives x to the sum, which is better than not including (which gives 0). So the maximum sum is the sum of all x where frequency >=x.
Wait, but wait: what about x=3 with frequency 4. So frequency =4 >=3. So including x=3 adds 3 to the sum. But could there be a case where including a higher x is better than including a lower x?
No, because each x's contribution is independent. For example, x=3 contributes 3, x=4 contributes 4, etc. So including all possible x's (where frequency >=x) will give the maximum possible sum.
Wait, but let's take an example where including a higher x may prevent including a lower x. Wait, but how? The frequency counts are for different x's. For example, the count of 2 is separate from the count of 3.
Wait, suppose we have an array where x=2 has frequency 2 (so can include, sum +=2), and x=3 has frequency 3 (sum +=3). Including both gives sum 5. Which is better than including either alone.
Yes, so there's no conflict. So the maximum sum is simply the sum of all x where frequency >=x.
Wait, but let's think of another example. Suppose x=2 has frequency 3 (so can include, sum +=2), and x=1 has frequency 1 (sum +=1). Total sum 3. Which is correct.
But what if x=1 has frequency 2. Then, since frequency[1] =2 >=1, including x=1 adds 1. But if we don't include x=1, but include x=2 (if possible), but x=2's frequency is say 2. Then sum is 2. Which is better than 1. So in this case, including x=2 is better. But according to our approach, we include both x=1 and x=2, sum is 1+2=3, which is better.
Wait, but x=1's frequency is 2 >=1, so including it adds 1. Even though the frequency is higher than x, we can still include it. Because the condition is that the count after deletion is exactly x. For x=1, even if there are 2 occurrences, we delete 1 to make it 1. So it's valid.
So including x=1 (with frequency 2) gives sum +=1. Which is better than not including (sum +=0). So yes, we should include it.
So the maximum sum is indeed the sum of all x where frequency >=x.
Wait, but wait another example. Suppose x=2 has frequency 3 (so can include, sum +=2), and x=3 has frequency 2 (which is less than 3, so cannot include). So sum is 2.
But what if x=2's frequency is 3, but x=1's frequency is 0. So sum is 2.
Yes.
Another example: x=2 has frequency 1. Since 1 <2, cannot include. So sum doesn't include 2.
So the approach seems correct.
Wait, but wait: what about x=5 with frequency 5. Then sum +=5. Which is good.
So, according to this, the algorithm is:
For each test case:
But wait, let's check the second sample test case:
Input: 5 elements [1,1,2,2,3]
n=5.
frequency:
x=1: 2 >=1 → add 1.
x=2: 2 >=2 → add 2.
x=3: 1 <3 → no.
sum_s =3.
answer=5-3=2. Correct.
Third test case:
n=10.
array: [1,2,3,2,4,4,4,4,5,2]
frequency:
x=1: 1 → 1 >=1 → add 1.
x=2: 3 → 3 >=2 → add 2.
x=3: 1 → no.
x=4:4 → yes → add4.
x=5:1 → no.
sum_s=1+2+4=7.
answer=10-7=3. Correct.
Fourth test case: n=1, array [0].
frequency[0] =1.
for x from 1 to 1:
x=1: frequency[1] is 0 <1 → no.
sum_s=0.
answer=1-0=1. Correct.
Another test case: [2,2,2], n=3.
x=2: frequency=3 >=2 → sum_s=2.
answer=3-2=1. Correct.
Another example: [1,1,1], n=3.
x=1: frequency=3 >=1 → sum_s=1.
answer=3-1=2. Which means delete 2 elements, leaving [1], which is balanced. Correct.
Wait, but [1] is balanced because 1 occurs once. Yes.
Another example: [1,1], n=2.
x=1: frequency=2 >=1 → sum_s=1.
answer=2-1=1. So delete 1 element, leaving [1], which is balanced. Correct.
But what if the array is [1,1,2,2], n=4.
x=1: frequency=2 >=1 → add 1.
x=2: frequency=2 >=2 → add 2.
sum_s=3.
answer=4-3=1.
Wait, but the balanced array would have 1 once and 2 twice. So total elements 3. So delete 1 element. Which one? For x=1, we need to delete 1 occurrence (since frequency is 2, need to get to 1). For x=2, frequency is 2, which is exactly 2, so no deletion. So total deletions 1. Correct.
Yes.
But according to our formula, sum_s is 1+2=3. deletions=4-3=1. Correct.
So this seems to hold.
Wait, but what about a case where including a higher x would be better than including multiple lower x's?
For example, suppose x=3 has frequency 3 (sum +=3), and x=1 and x=2 have frequencies >=1 and >=2.
sum_s would be 1+2+3=6.
But if for some reason, including x=3 prevents including x=1 and x=2, but in reality, they are independent.
No, because the frequencies are for different numbers. So including x=3 doesn't affect x=1 and x=2.
So the sum is additive.
Therefore, the maximum sum is indeed the sum of all x where frequency >=x.
So the algorithm is straightforward.
Now, what about x=0?
In the frequency count, x=0 is counted, but since x=0 cannot be part of S (as explained before), it's automatically excluded. So in the sum_s, x starts from 1.
Thus, the code steps are:
For each test case:
For each test case:
Read n.
Read the array of n integers.
Create a frequency array of size n+1 (since a_i can be up to n).
For each element in the array:
markdownCopy
if the element is 0, increment freq[0], but since 0 can't be in S, it's handled automatically.
sum_s =0
for x from 1 to n:
markdownCopy
if freq[x] >=x:
sum_s +=x
answer =n - sum_s
But wait, let's check the first sample test case:
Input: 3 elements [1,2,2]
n=3.
freq[1]=1, freq[2]=2.
sum_s=1 (x=1: 1>=1 yes) + 2 (x=2: 2>=2 yes) → sum_s=3.
answer=3-3=0. Correct.
Yes.
Another example: [2], n=1.
x=2: but n=1, so x can only be up to 1. Wait, no. Wait, the array elements can be up to n. For n=1, the array is [2]? No, because the input constraints say 0 ≤ a_i ≤n. So for n=1, a_i can be 0 or 1. So [2] is impossible.
Wait, the problem statement says for each test case, the array elements are 0 ≤ a_i ≤n. So for n=1, a_i can be 0 or 1.
So in the problem statement's example, the second test case is n=5, array includes 3, which is ≤5.
So in code, when building the frequency array, we need to consider x from 0 to n.
But in our sum_s, we loop x from 1 to n.
Now, let's code accordingly.
But wait, what if an element is larger than n? According to the problem statement, 0 ≤ a_i ≤n, so no.
Thus, the code can proceed.
Now, let's check the example where n=3, array is [3,3,3].
x=3: frequency=3. 3 >=3 → sum_s +=3.
answer=3-3=0. So the array is balanced. But [3,3,3] has 3 occurrences of 3, which is exactly 3. So yes, it's balanced. Correct.
Another example: n=4, array [3,3,3,3].
x=3: frequency=4 >=3 → sum_s +=3.
answer=4-3=1. So delete 1 element, resulting in 3 occurrences of 3. Which is balanced. Correct.
Wait, but 3 occurrences of 3 is exactly 3, which is correct.
Yes.
So the code seems correct.
Now, what about x=4 in n=4. If array is [4,4,4,4], frequency[4] =4. sum_s +=4. answer=4-4=0. Correct.
Another edge case: n=1, array [1]. sum_s=1 (x=1, freq=1 >=1). answer=0. Correct.
n=1, array [0]. sum_s=0. answer=1. Correct.
n=2, array [2,2]. sum_s=2 (x=2, freq=2 >=2). answer=0. Correct.
n=2, array [2,2,2] → but n=2? No, because n is the size of the array. Wait, for n=3, array [2,2,2], sum_s=2 (x=2, freq=3 >=2). answer=3-2=1. Correct.
Thus, the approach is correct.
Now, code in C++.
Steps:
-
Read t.
-
For each test case:
read n.
read n integers.
create a frequency vector of size n+1, initialized to 0.
for each number in the array:
if the number is between 0 and n (which it is, per problem statement), increment freq[number].
sum_s =0.
for x from 1 to n:
if freq[x] >=x:
sum_s +=x.
answer =n - sum_s.
output answer.
Wait, but what about numbers larger than n? According to the problem statement, a_i is between 0 and n, so no.
But in code, since the array elements are given as 0 ≤ a_i ≤n, we don't have to worry about numbers larger than n.
Wait, but for example, when n=3, the array could have 3 as an element. So the frequency array needs to be size n+1.
Yes.
Testing the code with the sample inputs.
Sample input:
4
3
1 2 2
5
1 1 2 2 3
10
1 2 3 2 4 4 4 4 5 2
1
0
Processing:
First test case: n=3, array [1,2,2].
freq[1]=1, freq[2]=2.
sum_s=1+2=3. answer=3-3=0. Output 0.
Second test case: n=5, array [1,1,2,2,3].
freq[1]=2, freq[2]=2, freq[3]=1.
sum_s=1 (x=1: 2>=1) +2 (x=2: 2>=2) =3. answer=5-3=2. Output 2.
Third test case: n=10, array [1,2,3,2,4,4,4,4,5,2].
freq[1]=1, freq[2]=3, freq[3]=1, freq[4]=4, freq[5]=1.
sum_s=1 (x=1) +2 (x=2) +4 (x=4) =7. answer=10-7=3. Output 3.
Fourth test case: n=1, array [0].
freq[0]=1. sum_s=0. answer=1-0=1. Output 1.
Which matches the sample output.
Thus, the code should work.
Now, code in C++.
Note: the input has multiple test cases. The first line is t (number of test cases). Then for each test case, n and the array.
Implement accordingly.
Let's write the code.
We'll use:
#include
#include
using namespace std;
int main() {
markdownCopy
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> freq(n+1, 0); // indices 0..n
for (int i=0; i<n; i++) {
int num;
cin >> num;
if (num >=0 && num <=n) {
freq[num]++;
}
// since problem states 0<=num<=n, the if is redundant but safe.
}
long long sum_s =0;
for (int x=1; x<=n; x++) {
if (freq[x] >=x) {
sum_s +=x;
}
}
cout << n - sum_s << endl;
}
return 0;
}
Wait, but what about numbers that are 0? They are counted in freq[0], but since we loop x from 1 to n, they are ignored. Which is correct.
Testing the fourth sample: n=1, array [0]. freq[0] is 1. sum_s=0. answer=1-0=1. Correct.
Another test case: n=3, array [0,0,0]. sum_s=0. answer=3-0=3. Which is correct, because all 0s must be deleted.
Yes.
Another test case: n=2, array [0, 2]. freq[0]=1, freq[2]=1.
sum_s: x=1: freq[1]=0 <1. x=2: freq[2]=1 <2. sum_s=0. answer=2-0=2. So delete both elements. Which is correct, because 0 must be deleted, and 2 has count 1 which is less than 2, so must delete it. Total deletions 2.
Yes.
Another test case: n=4, array [2,2,3,3,3]. Wait, n=5? No, n is given as 5. Let's say n=5, array [2,2,3,3,3].
freq[2]=2, freq[3]=3.
sum_s: x=2: 2 >=2 → add 2. x=3:3 >=3 → add3. sum_s=5. answer=5-5=0. So the array is already balanced. Indeed, 2 occurs 2 times, 3 occurs 3 times. Correct.
Yes.
Thus, the code should be correct.
But wait, in the problem statement, the example input has the third test case as n=10. Let's check:
The third test case input is:
10
1 2 3 2 4 4 4 4 5 2
So n=10, array elements are 1,2,3,2,4,4,4,4,5,2.
freq[1] =1, freq[2]=3, freq[3]=1, freq[4]=4, freq[5]=1.
sum_s =1+2+4=7. 10-7=3. Correct.
Yes.
So the code should work.
But wait, what about x=0? For example, in the array [0,1,1], n=3.
freq[0]=1, freq[1]=2.
sum_s: x=1: 2 >=1 → add 1. sum_s=1. answer=3-1=2.
Which means delete 2 elements. The balanced array would have one 1. So delete 0 and one 1. Total deletions 2. Correct.
Yes.
Another case: array [0, 1], n=2.
sum_s: x=1: freq=1 >=1 → sum_s=1. answer=2-1=1. So delete 0 and keep 1. Which is correct.
Yes.
Thus, the code should handle all cases correctly.
Now, check constraints.
t up to 500, n up to 100.
The code loops for each test case, for n up to 100, and for x from 1 to n (100 steps). So 500 * 100 = 50,000 operations, which is acceptable.
Yes.
Thus, the code is correct.
To solve this problem, we need to determine the minimum number of elements to delete from an array so that the resulting array is balanced. A balanced array is defined as one where every integer ( x ) that appears in the array occurs exactly ( x ) times.
This approach efficiently checks each possible ( x ) to determine if it can contribute to a balanced array, leveraging the insight that maximizing the sum of valid ( x ) values minimizes deletions. The solution handles all edge cases, including arrays with zeros (which must be entirely deleted) and numbers appearing more or less than required. The complexity is ( O(t \cdot n) ), which is optimal given the constraints.
테스트 사이트에서 K-EXAON 236 B 는 context 제약사항으로, 중간중간 잘리게 됩니다.
그래서 continue 를 계속하여 마지막에 결과 c++ 코드가 나오게 하였으나
그 코드는 컴파일이 안되거나, wrong answer 가 나왔습니다.
출력 context 가 2000개로 제한되어 동등한 비교가 힘든거 같습니다.
K-EXAON 236B 모델의 context 를 20000 개 정도로 확장했으면 합니다.
K-EXAONE vs. Qwen3: 무엇이 다른가?
"직접 써보고 판단하세요" (Side-by-Side 비교 팁)
지금 바로 확인해야 하는 이유
