【蓝桥等考C++真题】蓝桥杯等级考试C++组第13级L13真题原题(含答案)-套娃

C++L13 套娃(30 分)

• 套娃是俄罗斯特产的木制玩具，由许多个图案一样的空心娃娃一个套一个组成。
• 桌子上有 n 个娃娃，包括 5 种型号，分别是 1~5 号，1 号最小，5 号最大。
• 大的娃娃可以套在比它更小的娃娃外面，如果这样做，你只能看见一个大娃娃。
• 现在要把这 n 个娃娃，能套在一起的都套起来，
• 问，能凑成几套完整的套娃？桌子上最少能看见几个娃娃？

例如，有 10 个娃娃，型号分别是 1,3,1,2,1,5,2,3,4,5。
可以凑成 1 套完整的：因为 4 号娃娃最少，只有 1 个；
桌子上最少能看见 3 个娃娃，因为能套的都已经套起来了，
包括：一套完整的：{1,2,3,4,5}，两套不完整的：{1,2,3,5}和{1}。

• 输入：

第一行是一个正整数 n(n<=100,000)代表娃娃数量；
第二行包含 n 个 1~5 的整数，代表每个娃娃的型号：相邻两个整数之间用空格隔开。

• 输出：

第一行一个整数，为能凑成完整套娃的数量；
第二行一个整数，为桌子上最少能看见的娃娃的数量。

• 输入样例 1：

10
1 3 1 2 1 5 2 3 4 5

• 输出样例 1：

1
3

能凑成几套完整的套娃取决于型号最大的娃娃的数量。
例如，如果 5 号娃娃最少，只有 1 个，那么无论如何也凑不出 2 套完整的套娃。
而最少能看见几个娃娃取决于数量最多的那个型号的娃娃的个数。
假设 3 号娃娃最多，有 6 个，
那么比 3 号小的娃娃可以套在 3 号里面，比 3 号大的娃娃可以把 3 号套住，
此时桌面上最少能看见的娃娃依然是 6 个。

#include<bits/stdc++.h>
using namespace std;
int a[6]; //桶排序数组, 表示1-5号娃娃出现的次数
int main(){
	int n,m;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>m; //m号娃娃
		a[m]++; //m号娃娃每出现一次累加1
	}
	sort(a,a+6); //按照出现次数排序
	for(int i=1;i<=5;i++)
		if(a[i]){ //为防止输出出现零次的娃娃,有值才输出
			cout<<a[i]<<endl;
			break; //只输出出现次数最少的娃娃, 然后跳出
		}
	cout<<a[5]; //再输出出现次数最多的娃娃
	return 0;
}