P11006 [蓝桥杯 2024 省 Python B] 纯职业小组

题目描述

在蓝桥王国，国王统治着一支由 $n$ 个小队组成的强大军队。每个小队都由
相同职业的士兵组成。具体地，第 $i$ 个小队包含了 $b_i$ 名职业为 $a_i$ 的士兵。

近日，国王计划在王宫广场举行一场盛大的士兵检阅仪式，以庆祝王国的繁荣昌盛。然而，在士兵们入场的过程中，一场突如其来的风暴打乱了他们的行列，使得不同小队的士兵混杂在一起，次序乱成一团，

尽管国王无法知道每个士兵的具体职业，但为了确保仪式能顺利进行，国王打算从这些混乱的士兵中选出一部分，组成 $k$ 个“纯职业小组”进行检阅。一个“纯职业小组”定义为由 $3$ 名同职业的士兵组成的队伍。

请问，国王至少需要选择多少名士兵，才能确保这些士兵可以组成 $k$ 个“纯职业小组”？

输入格式

输入的第一行包含一个整数 $T$，表示每次输入包含 $T$ 组数据。

接下来依次描述 $T$ 组数据。

每组数据的第一行包含两个整数 $n_t$ 和 $k$ ，用一个空格分隔，表示小队的数量和要组成的纯职业小组的数量。

接下来的 $n_t$ 行，每行包含两个整数 $a_i$ 和 $b_i$，用一个空格分隔，表示第 $i$ 个小队中士兵的职业和数量。

输出格式

输出 $T$ 行，每行包含一个整数，依次表示每组数据的答案，即为了组成 $k$
个“纯职业小组”，国王至少需要选择的士兵数量。如果无论如何也无法组成 $k$ 个“纯职业小组”，则输出 $-1$。

输入输出样例 #1

输入 #1

2
3 2
1 3
2 3
3 3
3 5
1 3
2 3
3 3

输出 #1

8
-1

说明/提示

对于 $50\%$ 的评测用例，$1\le T\le 10，1\le {\sum }_{t=1}^T{n}_t\le 2\times 10^3,1\le a_i,b_i\le 10^5,1\le k\le 10^7$。

对于所有评测用例，$1\le T\le 100，1\le {\sum }_{t=1}^T{n}_t\le 2\times 10^5,1\le a_i,b_i\le 10^9,1\le k\le 10^{13}$。

样例解释

在第一个样例中，要想组成 $2$ 个“纯职业小组”，国王至少需要选择 $8$ 名
士兵。若只选择了 $7$ 名士兵，则这 7 名士兵的职业可能为 $1,1,1,2,2,3,3$，无法组成 $2$ 个“纯职业小组”。

在第二个样例中，即使选择了所有士兵，也无法组成 $5$ 个“纯职业小组”，
因此输出 $-1$。

C++实现

#include<iostream>
#include<map>
#define int long long
using namespace std;
int n,k,sum,cnt,res,f[3];
map <int,int> t;
void sol()
{
	cin>>n>>k,k--,sum=res=cnt=f[1]=f[2]=0,t.clear();
	for(int i=1,x,y;i<=n;i++) cin>>x>>y,t[x]+=y;
	for(auto te:t)
	{
		int x=te.second; sum+=x/3;
		if(x<=2) res+=x;
		else res+=2,cnt+=((x-2)/3),f[(x-2)%3]++;
	}
	if(sum<k) {cout<<-1<<'\n'; return;}
	cnt=min(cnt,k),res+=cnt*3,k-=cnt;
	for(int i=2;i>=1;i--)
	{
		int tx=min(f[i],k);
		k-=tx,res+=tx*i;
	}
	cout<<res+1<<'\n';
} 
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int TT; cin>>TT;
	while(TT--) sol();
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容