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

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

Easy 记负均正

简要题意

给 个整数，求其中负数个数和正数均值。

Solution

记录正负数个数与正数和即可。

Code

void R()
{
	int n,pos=0,neg=0,sum=0;
	cin>>n;
	for (int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		if (x<0) neg++;
		if (x>0) pos++,sum+=x;
	}
	cout<<neg<<' ';
	if (pos)
		cout<<fixed<<setprecision(7)<<double(sum)/pos;
	else cout<<0;
	return;
}

Medium 小数字

简要题意

给一个数字 ，可以做 次操作，操作为以下三选一：

• 若 非负，可以对其开方上取整。

• 令 减 。

• 对 除 向上取整。

求操作后 的最小值。

Solution

时只会做减一操作， 的时候就算只选操作一步数也是 的，而结果显然是关于 单调递减的，所以直接暴力取三种操作中答案最小的一个就好。

Code

int ceilDiv(int n,int m)
{
	if (n>=0) return (n+m-1)/m;
	else return n/m;
}

void R()
{
	int n,m;
	cin>>n>>m;
	while (m)
	{
		int t=min(n-1,ceilDiv(n,2));
		if (t>0) t=min(t,int(ceil(sqrt(n))));
		else
		{
			n-=m;
			break;
		}
		if (t==n) break;
		n=t,m--;
	}
	cout<<n<<'\n';
	return;
}

Hard 【模板】完全背包

简要题意

给一个容量为 的背包和 种体积为 重量为 的物品各任意个，求向包中放入某些物品/放满背包后，包中物品的最大价值。

Solution

跟上一天的题类似，都是背包，区别在于一种物品可以重复选取，所以在实现时我们可以正着递推。

设 代表背包已占用 空间的最大价值。

考虑放入一个体积为 重量为 的物品，有转移：

答案分别是 数组最大值和最后一位。

Code

void R()
{
	int n,V;
	cin>>n>>V;
	vector<int> dp(V+1);
	for (int i=0;i<n;i++)
	{
		int v,w;
		cin>>v>>w;
		for (int j=v;j<=V;j++)
			if (dp[j-v]||j==v)
				dp[j]=max(dp[j],dp[j-v]+w);
	}
	cout<<*max_element(dp.begin(),dp.end())<<'\n'<<dp[V];
	return;
}