P11006 题解

KSCD_ · 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;
}