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

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

简单题 输入n个整数，输出其中最小的k个

排序后输出前 项。

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
print(*a[:k])

中等题 记票统计

使用数组记录票数，使用map记录选票对应的票数数组下标。
无效票可用 下标记录。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<string> c(n + 1);
    for (int i = 1; i <= n; i++)cin >> c[i];
    map<string, int> mp;
    vector<int> numbers(n + 1);
    for (int i = 1; i <= n; i++)mp[c[i]] = i;
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        string v;
        cin >> v;
        numbers[mp[v]]++;
    }
    for (int i = 1; i <= n; i++)
        cout << c[i] << " : " << numbers[i] << "\n";
    cout << "Invalid : " << numbers[0] << "\n";
    return 0;
}

困难题 哈夫曼编码

堆的模板题。
每次从堆中取出两个频率最小的数，答案加上这两个数的和，再将两数之和加入堆中。
反映到哈夫曼编码上，就是取出两个频率最小的编码，这两个编码的长度 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)cin >> a[i];
    priority_queue<long long, vector<long long>, greater<long long>> pq;
    for (int i = 0; i < n; i++)pq.push(a[i]);
    long long ans = 0;
    while (pq.size() >= 2) {
        long long a = pq.top();
        pq.pop();
        long long b = pq.top();
        pq.pop();
        ans += a + b;
        pq.push(a + b);
    }
    cout << ans << '\n';
    return 0;
}