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

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

Easy 一封奇怪的信

简要题意

钦定每个小写字母一个权值。给定一个小写字母串，求将其分行书写，保证每行权值和不超过 的条件下，最小书写行数以及此时末行最短长度。

Solution

直接模拟即可。

Code

void R()
{
	vector<int> w(26);
	string s;
	for (int &x:w) cin>>x;
	cin>>s;

	int now=0,cnt=1;
	for (char c:s)
	{
		int p=c-'a';
		if (now+w[p]>100)
			cnt++,now=w[p];
		else now+=w[p];
	}
	cout<<cnt<<' '<<now<<'\n';
	return;
}

Medium 小球投盒

简要题意

有 个空盒与 次操作，每次操作为下列二者之一：

• 选一个盒放入一球

• 选一个盒，对其余所有盒各放入一球

求最早在第几次操作后每盒内都有球。

Solution

用 set 维护空盒。

第一个操作就是删去某盒。

第二个操作就是只留下某盒，如果该盒已被删去就结束。

Code

void R()
{
	int n,m,ans=-1;
	cin>>n>>m;
	set<int> s;
	for (int i=1;i<=n;i++)
		s.insert(i);
	for (int i=1;i<=m;i++)
	{
		int t,x;
		cin>>t>>x;
		if (t==1) s.erase(x);
		else
		{
			if (s.count(x))
			{
				s.clear();
				s.insert(x);
			}
			else s.clear();
		}
		if (ans==-1&&s.empty())
			ans=i;
	}
	cout<<ans;
	return;
}

Hard 请客吃饭

简要题意

给定 对 。选出若干对，使得选中的 时 的最小值。

Solution

按 排序，枚举 双指针更新答案。

Code

void R()
{
	i64 n,k,ans=-1;
	cin>>n>>k;
	vector<pair<i64,i64>> a(n);
	for (auto &p:a) cin>>p.first;
	for (auto &p:a) cin>>p.second;
	sort(a.begin(),a.end());

	i64 sum=a[0].second;
	for (int l=0,r=0;l<n;sum-=a[l].second,l++)
	{
		while (sum<k)
		{
			r++;
			if (r>=n)
			{
				cout<<ans;
				return;
			}
			sum+=a[r].second;
		}
		if (ans==-1) ans=a[r].first-a[l].first;
		else ans=min(ans,a[r].first-a[l].first);
	}
	cout<<ans;
	return;
}