Balloons
National Olympiad — Municipal round
Submission name: colors.cpp
Problem summary
Choose exactly K of N colored balloons. Maximize the number of different colors. Among all optimal choices, output the lexicographically smallest color sequence. You may order the chosen balloons freely.
Input
N K, followed by N integer color labels.
Output
The K selected labels in nondecreasing order.
Constraints
1 ≤ N ≤ 100,000; 1 ≤ K ≤ min(N, 50,000); colors: 1…25,000.
Worked example
An independently prepared example for this explanation.
Input
7 4 3 1 3 2 1 3 4
Output
1 2 3 4
Solution analysis
- Count balloons of each color. Let D be the number of available colors.
- If K < D, use one balloon of each of the K smallest colors. No repetition is needed.
- Otherwise reserve one of every color. Spend the remaining K−D slots on additional balloons, starting with the smallest color.
- Print chosen counts in ascending color order.
Why it works
No selection can contain more than min(K,D) colors, and this construction reaches that bound. Once one of each required color is reserved, replacing a larger extra color with an available smaller one preserves diversity and improves the sorted sequence.
Watch out. Do not simply take the K smallest balloons: that can lose distinct colors.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,k;
cin>>n>>k;
const int C=25000;
vector<int>count(C+1),take(C+1);
for(int i=0,color;i<n;++i){
cin>>color;
++count[color];
}
int distinct=0;
for(int c=1;c<=C;++c){
distinct+=(count[c]>0);
}
int remaining=k;
// Reserve as many different colors as possible, smallest first.
for(int c=1;c<=C&&remaining;++c){
if(count[c]){
take[c]=1;
--remaining;
}
}
// If all colors were reserved, fill remaining places cheaply.
for(int c=1;c<=C&&remaining;++c){
int extra=min(remaining,count[c]-take[c]);
take[c]+=extra;
remaining-=extra;
}
bool first=true;
for(int c=1;c<=C;++c){
for(int j=0;j<take[c];++j){
if(!first){
cout<<' ';
}
first=false;
cout<<c;
}
}
cout<<'\n';
}