自动搬运

查看原文

来自洛谷，原作者为

	KSCD_ 知不可乎骤得，知来者之可追. | Defection,Retribution,Testify. | Rotating_Catfood

搬运于2025-08-24 23:03:24，当前版本为作者最后更新于2024-09-24 10:51:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

有多种士兵，每种有若干个，求最小的 $x$ 使得任意选出 $x$ 名士兵均能保证可以选出 $k$ 个三人组，且每个组中的三人种类相同。

思路

转化成逆命题即为：求最大的 $y$ 使得存在一种选出 $y$ 名士兵的方案，在这 $y$ 名士兵中无法选出 $k$ 个种类相同的三人组。那么选出 $(y+1)$ 名士兵时就一定满足题意，所以最小的 $x$ 即为 $y+1$。

考虑怎么计算出最大的 $y$，发现可以先从每种里取 $2$ 名士兵，之后再取 $1$ 名时，若剩余数量足够，直接同时多取 $2$ 名，也就是取 $3$ 名；若剩余数量不够，则一定无法再组成更多三人组，也直接把剩下的全部取出。

这样保证了在剩余士兵中任取一名即可组成一个新的三人组，也就能在保证三人组数量最少的前提下取出尽可能多的士兵。那么能组成 $(k-1)$ 个三人组时取出的士兵数即为要求的 $y$。

实现上可以用 map 存储每个种类的士兵数，当然也可以离散化 + 桶记录。特判无解后每种先取出 $2$ 名，统计剩余足够 $3$ 名士兵的数量 $cnt$，把剩余的 $1,2$ 数量记在 $f_1,f_2$ 中，依次取出即可。

代码

#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;
}