Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Balanced only cares about the final frequency of each distinct value. The positions of elements are completely irrelevant.
Look at one value independently. If it appears times, your final array can keep either exactly copies of it, or zero copies of it.
If , you cannot keep copies because deletions cannot create elements. So all copies must go.
If and , keeping exactly copies costs deletions, while deleting all of them costs . Keeping is always at least as good.
Special case: value can never appear in a balanced array, because it would need to appear exactly times. So count frequencies and add if or , otherwise add .
For every value, we only care about how many times it appears. The array order is noise. Delete it from your brain.
Suppose some value appears times.
In the final balanced array, if appears at all, it must appear exactly times. Since we can only delete elements, there are only two possible outcomes for this value:
There is no third option. Keeping copy of value is invalid. Keeping copies of value is invalid. Balanced means the frequency must equal the value itself.
When can we keep value ?
We can keep it only if we already have at least copies, meaning:
If , we cannot magically create more copies, so we must delete all occurrences.
If and , then keeping exactly copies costs:
deletions. Deleting all copies costs:
Since , keeping exactly copies is always optimal whenever possible.
Now for the tiny annoying caveat: .
If value appears, then for the array to be balanced, it would need to appear exactly times. But if it appears at least once, that is already impossible. So every zero must be deleted. Classic little statement trap, nothing too evil.
So for each value with frequency :
Add these costs over all values.
Why this greedy works: decisions for different values never interact. Deleting a 2 does not affect how many 4s you have. So optimizing each value separately gives the global minimum. No DP, no sorting required, no ritual sacrifice to the complexity gods.
The constraints are tiny anyway: , . A frequency array of size is enough because .
Complexity:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> freq(n + 1, 0);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
freq[x]++;
}
int ans = 0;
for (int x = 0; x <= n; x++) {
int c = freq[x];
if (x == 0 || c < x) ans += c;
else ans += c - x;
}
cout << ans << '\n';
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> freq(n + 1, 0);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
freq[x]++;
}
int ans = 0;
for (int x = 0; x <= n; x++) {
int c = freq[x];
if (x == 0 || c < x) ans += c;
else ans += c - x;
}
cout << ans << '\n';
}
return 0;
}