题目描述

在蓝桥王国，国王统治着一支由n个小队组成的强大军队。每个小队都由相同职业的士兵组成。
具体地，第 i个小队包含了 bi名职业为 ai的士兵。
近日，国王计划在王宫广场举行一场盛大的士兵检阅式，以庆祝王国的繁荣昌盛。

然而，在士兵们入场的过程中，一场突如其来的风暴打乱了他们的行列，使得不同小队的士兵混杂在一起，次序乱成一团。

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

一个“纯职业小组”定义为由3名同职业的士兵组成的队伍。

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

算法1

$O(nlogn)$

C++ 代码

#include<map>
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N=2e5+10;
int t,n,k,x,y;
map<int,int> mp;
void solve(){
    mp.clear();
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>x>>y;
        mp[x]+=y;
    }
    int a[N],js=0,Max=0,Min=0,num=0;
    for(auto i:mp){
        int p=i.second;
        if(p<3){
            Min+=p;
            continue;
        }
        Max+=(p/3);
        a[js++]=(p%3+1);
        num+=(p-p%3-1)/3;
        Min+=((p-p%3-1)/3*3+2);
    }
    int ans=Min;
    sort(a,a+js);
    if(Max<k)ans=-1;
    else if(num<k){
        int j=0;
        for(int i=js-1;i>=0&&j<k-num;i--)j++,ans+=a[i];

    }
    else ans-=((num-k)*3+2);
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--)solve();
    return 0;
}