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

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

Easy 分组

简要题意

有 个同学进行分组，要求每组不少于 人，问最多分几组。

Solution

显然答案就是 。

Code

void R()
{
	int n;
	cin>>n;
	cout<<n/3;
	return;
}

Medium 小欧的数组修改

简要题意

给一个数组，你可以选择一个数进行修改，之后求数组众数出现次数最大值。

Solution

如果数组内只有一种数，答案就是 ；否则就是原数组众数出现次数 。

Code

void R()
{
	int n,ans=0;
	cin>>n;
	map<int,int> cnt;
	for (int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		cnt[x]++;
		ans=max(ans,cnt[x]);
	}
	if (ans<n) ans++;
	cout<<ans;
	return;
}

Hard 合唱队形

简要题意

问至少删去多少个数，可以使给定数组先严格上升后严格下降（允许全程严格上升或下降）。

Solution

我们把先严格上升后严格下降的序列称为合唱序列。

题目相当于求 减去数组中最长合唱序列长度。

dp 出从前往后/从后往前每个位置的最长上升子序列 。

就是以位置 为最大值的最大合唱序列长度，取 即为答案。

Code

void R()
{
	int n,ans=0;
	cin>>n;
	vector<int> t(n),f(n),g(n);
	for (int &x:t) cin>>x;
	for (int i=0;i<n;i++)
	{
		f[i]=1;
		for (int j=0;j<i;j++)
			if (t[j]<t[i])
				f[i]=max(f[i],f[j]+1);
	}
	for (int i=n-1;i>=0;i--)
	{
		g[i]=1;
		for (int j=n-1;j>i;j--)
			if (t[i]>t[j])
				g[i]=max(g[i],g[j]+1);
	}
	for (int i=0;i<n;i++)
		ans=max(ans,f[i]+g[i]-1);
	cout<<n-ans;
	return;
}