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

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

简单题 分组

每一组不能少于 个人，最多能分成 组。

print(int(input()) // 3)

中等题 小欧的数组修改

如果数组全为一种数，答案就是 。
否则，修改一个元素，使这个元素变成出现次数最多的元素，答案是最多出现次数的元素的出现次数 。
因为 ，所以可以使用大小为 的数组记录出现次数。
时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> cnt(100005);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }
    int maxcnt = *max_element(cnt.begin(), cnt.end());
    cout << min(maxcnt + 1, n) << '\n';
}

困难题 合唱队形

枚举 ，问题转化成求最大的在 的最长上升子序列长度 在 的最长下降子序列长度。
设 表示 的最长上升子序列长度和在 的最长下降子序列长度。
因为 ，使用常规的 dp方法求即可。


因为求的是最少的出列人数，所以答案为 。
时间复杂度 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1), dp1(n+1, 1), dp2(n+1, 1);
    for (int i = 1; i <= n; i++)cin >> a[i];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < i; j++)
            if (a[j] < a[i])
                dp1[i] = max(dp1[i], dp1[j] + 1);
    for (int i = n; i >= 0; i--)
        for (int j = n; j > i; j--)
            if (a[j] < a[i])
                dp2[i] = max(dp2[i], dp2[j] + 1);
    int ans = n;
    for (int i = 1; i <= n; i++)
        ans = min(ans, n - dp1[i] - dp2[i] + 1);
    cout << ans << '\n';
    return 0;
}