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

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

简单题 小苯的比赛上分

使用优先队列维护贪心。
创建一个小根堆，会保证堆顶元素一定是最小元素，每一步操作如下：
每次取出堆顶元素 ，将 加入堆中。
初值为 ，每一步操作需要更新 ： 。

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

中等题 小欧安排座位

如果只有 个独特小朋友，则无法满足这个小朋友的需求。
否则，可以将独特小朋友连成一个环。
设独特小朋友共有 个，编号为 ，则可以让 号小朋友坐 号座位， 号小朋友坐 号座位，……，第 号小朋友坐 号座位。
安排后这些小朋友分别坐在 号座位。
这样能满足所有小朋友的需求。
程序实现上，可以将 数组循环左移一位，或者从左到右，每两个相邻元素都交换一次。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    iota(a.begin(), a.end(), 0);
    string s;
    cin >> s;
    vector<int> d;
    for (int i = 0; i < n; i++)
        if (s[i] == '1')
            d.push_back(i + 1);
    for (int i = 0; i + 1 < d.size(); i++)
        swap(a[d[i]], a[d[i + 1]]);
    for (int i = 1; i <= n; i++)cout << a[i] << " \n"[i == n];
    return 0;
}

困难题 小苯的数字权值

可以表示成若干个质数的乘积：。
则这个数的权值为 。
另一个方案是全部拆成质因子，拆开后的权值为 。
当 有 个及以上质因子，不拆开是权值更大的，因为乘积的每一项都大于等于 。
当 只有 个质因子，拆开是权值更大的。
或者，不用考虑 的质因子个数，直接计算不拆开和全部拆开的权值，两种权值取最大值输出。

#include <bits/stdc++.h>
using namespace std;
void solve() {
    int x;
    cin >> x;
    long long ans1 = 1, ans2 = 0;
    map<int, int> mp;
    for (int i = 2; i <= sqrt(x); i++) {
        while (x % i == 0) {
            mp[i]++;
            x /= i;
        }
    }
    if (x != 1)mp[x]++;
    for (auto [_, y] : mp) {
        ans1 *= (y + 1);
        ans2 += 2 * y;
    }
    cout << max(ans1, ans2) << '\n';
}
int main() {
    int t;
    cin >> t;
    while (t--)solve();
    return 0;
}