牛客春招刷题训练营 - 2025.4.2 题解

活动地址：牛客春招刷题训练营 - 编程打卡活动

Easy 输入n个整数，输出其中最小的k个

简要题意

如题。

Solution

直接用 sort() 对数组排序后输出前 个数即可。

Code

void R()
{
	int n,k;
	cin>>n>>k;
	vector<int> a(n);
	for (int &x:a) cin>>x;
	sort(a.begin(),a.end());
	for (int i=0;i<k;i++)
		cout<<a[i]<<" \n"[i+1==k];
	return;
}

Medium 记票统计

简要题意

给 个字符串，分别表示 位候选人名字。

给 个字符串，分别表示 张票上写的名字。

若某张票上写的名字不是某位候选人的名字，这张票无效；否则给这位候选人投一票。

求各位候选人的票数和无效票数。

Solution

用 map 记录每个名字是否为候选人名字、每个候选人的票数，然后模拟就好。

Code

void R()
{
	int n,m,inv=0;
	cin>>n;
	vector<string> s(n);
	map<string,bool> vis;
	map<string,int> cnt;

	for (auto &x:s) cin>>x;
	for (auto &x:s) vis[x]=1;

	cin>>m;
	for (int i=0;i<m;i++)
	{
		string t;
		cin>>t;
		if (vis.count(t))
			cnt[t]++;
		else inv++;
	}

	for (auto &x:s)
		cout<<x<<" : "<<cnt[x]<<'\n';
	cout<<"Invalid : "<<inv;
	return;
}

Hard 【模板】哈夫曼编码

简要题意

给定某个字符串中各字母出现次数，求该字符串的哈夫曼编码长度。

Solution

哈夫曼编码就是将串中的每个字符表示成一个 串，使得所有字符的表示两两不为对方的前缀。

可以把这个问题转换为一个等价但更易懂的问题：

最初桌上有 块橡皮泥，每块橡皮泥有自己的重量。

你可以花费两块橡皮泥重量之和的力气，将这两块橡皮泥粘到一起。

求把 块橡皮泥粘成一块最少要花费多少力气。

怎么做？其实每次取当前桌上最轻的两块橡皮泥粘起来就好了。

证明：

我们可以把合并过程看成一棵二叉树，最初的各个橡皮泥就是二叉树的叶子（事实上这个结构就是哈夫曼树）。

那么答案就是每个叶子的重量乘上自己的深度。

如果最小的两个叶子不是最深，跟最深的两个节点交换一下一定不劣。

对于同一深度的叶子节点，互换位置对答案没有影响。

所以第一步选最轻的两个合并最优。

之后我们得到一个相同的子问题，所以反复取最轻的两个合并最优。

用堆模拟这个过程就能得到答案了。

Code

void R()
{
	int n;
	i64 ans=0;
	priority_queue<i64,vector<i64>,greater<i64>> q;
	cin>>n;
	for (int i=0;i<n;i++)
	{
		i64 x;
		cin>>x;
		q.push(x);
	}
	while (q.size()>1)
	{
		i64 x=q.top();
		q.pop();
		i64 y=q.top();
		q.pop();
		ans+=x+y;
		q.push(x+y);
	}
	cout<<ans<<'\n';
	return;
}