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

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

简单题 一封奇怪的信

模拟题。
记录当前行的宽度和行数，遍历字符串，如果当前行的宽度加上当前字符宽度 则开始下一行并把当前行的宽度清零。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int len[26];
    for (int i = 0; i < 26; i++)cin >> len[i];
    int lastline = 0, lines = 1;
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); i++) {
        if (len[s[i] - 'a'] + lastline > 100) {
            lines++;
            lastline = 0;
        }
        lastline += len[s[i] - 'a'];
    }
    cout << lines << ' ' << lastline << '\n';
    return 0;
}

中等题 小球投盒

完成目标共有三种可能：

1. 对某一个 使用了操作 和操作 。
2. 对 到 都使用了操作 。
3. 使用了两次操作 ，这两次操作的 不相同。

使用两个 set 记录使用过操作 的所有 和操作 的所有 。
遍历操作，如果当前 在两个 set 里都出现过，或者操作 的 set 大小等于 ，或者操作 的 set 大小大于等于 ，则完成目标。
时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    set<int> s1, s2;
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int t, x;
        cin >> t >> x;
        if (t == 1) {
            s1.insert(x);
            if (s2.count(x)) {
                cout << i;
                return 0;
            }
        } else {
            s2.insert(x);
            if (s1.count(x)) {
                cout << i;
                return 0;
            }
        }
        if (s1.size() == n || s2.size() >= 2) {
            cout << i;
            return 0;
        }
    }
    cout << -1;
    return 0;
}

困难题 请客吃饭

滑动窗口/双指针。
先对客人按照财富值升序排序，排序关键字可以与愉悦值无关。
以下均按 下标开始。
初始设置 ， 为窗口边界， 为愉悦值的和， 为当前答案。
如果 且 ，则当前窗口不满足条件，需要扩大窗口，先将窗口右边界右移，再 。
否则 ，再将窗口左边界右移。
操作完成后，如果 ，更新 。
最后 为 ，输出 ，否则输出 。
时间复杂度 ，复杂度主要在排序上，滑动窗口是 的。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    long long k;
    cin >> n >> k;
    vector<pair<int, long long>> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i].first;
    for (int i = 0; i < n; i++)
        cin >> a[i].second;
    sort(a.begin(), a.end());
    long long sum = 0;
    int minans = 2e9, l = 0, r = -1;
    while (l < n)
    {
        if (sum < k && r < n)
        {
            r++;
            if(r < n)
                sum += a[r].second;
        }
        else
        {
            sum -= a[l].second;
            l++;
        }
        if (sum >= k)
        {
            minans = min(minans, a[r].first - a[l].first);
        }
    }
    if (minans >= 2e9)
        minans = -1;
    cout << minans << '\n';
    return 0;
}