问题描述

在蓝桥王国，国王统治着一支由 nn 个小队组成的强大军队。每个小队都由相同职业的士兵组成。具体地，第 ii 个小队包含了 bibi​ 名职业为 aiai​ 的士兵。

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

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

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

输入格式

输入包含多组数据。

第一行包含一个整数 TT，表示有 TT 组数据。

对于每组数据：

• 第一行包含两个整数 ntnt​ 和 kk，表示小队的数量和要组成的纯职业小组的数量。
• 接下来的 ntnt​ 行，每行包含两个整数 aiai​ 和 bibi​，表示第 ii 个小队中士兵的职业和数量。

输出格式

对于每组数据，输出一个整数，表示为了组成 kk 个“纯职业小组”，国王至少需要选择的士兵数量。如果无论如何也无法组成 kk 个“纯职业小组”，则输出 −1−1。

样例输入

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

样例输出

8
-1

样例说明

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

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

评测用例规模与约定

对于 50%50% 的评测用例，1≤T≤101≤T≤10，1≤∑t=1Tnt≤2×1031≤t=1∑T​nt​≤2×103，1≤ai,bi≤1051≤ai​,bi​≤105，1≤k≤1071≤k≤107。

对于所有的评测用例，1≤T≤1001≤T≤100，1≤∑t=1Tnt≤2×1051≤t=1∑T​nt​≤2×105，1≤ai,bi≤1091≤ai​,bi​≤109，1≤k≤10131≤k≤1013。

运行限制

语言	最大运行时间	最大运行内存
C++	1s	256M
C	1s	256M
Java	3s	512M
Python3	10s	512M
PyPy3	3s	512M
Go	5s	512M
JavaScript	5s	512M

总通过次数: 2649  |  总提交次数: 6115  |  通过率: 43.3%

难度: 简单   标签: 思维, 省赛, 2024

算法思路

为了解决“纯职业小组”问题，我们需要确保在最坏情况下，国王选择足够数量的士兵以组成k个纯职业小组（每组3名同职业士兵）。以下是算法的核心思路：

1. ​​问题分析​​：

   • 每个小队有职业和士兵数量，士兵被打乱后混合。
   • 需确保无论士兵如何选择，都能组成k个纯职业小组。
   • 若所有小队士兵总数不足3k或小队提供的团队数不足k，则输出-1。
   • 否则，计算最坏情况下所需的最小士兵数。

2. ​​关键策略​​：

   • ​​最坏情况分析​​：敌人（命运）会尽量拖延形成小组，优先选择不同职业的士兵，直到不得不形成小组。
   • ​​初始选择​​：对每个职业选择至多2名士兵（避免形成小组）。
   • ​​团队形成​​：在初始选择后，额外选择士兵以强制形成k个小组：
     • 形成第一个小组需要额外1名士兵（使某个职业达到3人）。
     • 后续团队根据剩余资源（按余数分类）以不同成本形成。

3. ​​资源分类​​：

   • ​​c3​​：剩余士兵数可被3整除的职业数（每个团队消耗3名士兵）。
   • ​​c2​​：余数为2的职业数（每个团队消耗2名士兵）。
   • ​​c1​​：余数为1的职业数（每个团队消耗1名士兵）。

4. ​​算法步骤​​：

   • ​​步骤1​​：检查是否可行（总团队数 ≥ k）。
   • ​​步骤2​​：初始选择每个职业至多2名士兵。
   • ​​步骤3​​：分类剩余士兵资源（c3、c2、c1）。
   • ​​步骤4​​：形成第一个团队（消耗1名士兵）。
   • ​​步骤5​​：优先使用c3资源（高效），然后c2和c1。

算法过程演示

考虑样例输入：3个小队，每队3名士兵，k=2。

1. ​​初始状态​​：

   • 小队：[1:3, 2:3, 3:3]
   • 总团队数：3（每个小队提供1个团队），可行。

2. ​​初始选择​​：

   • 每个小队选2名士兵：已选士兵数 = 6（小队剩余：[1:1, 2:1, 3:1]）。

3. ​​资源分类​​：

   • 剩余士兵：每个小队余1（c1=3，c2=0，c3=0）。

4. ​​形成团队​​：

   • 形成第1个团队：额外选1名士兵（总士兵=7），使某个职业达到3人（如职业1）。
   • 形成第2个团队：使用c1资源（消耗1名士兵），总士兵=8。

最终，士兵数=8，可组成2个团队。

C++代码实现

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef long long LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int nt;
        LL k;
        cin >> nt >> k;
        map<int, LL> professionMap;
        vector<LL> b_arr;

        // 读入数据并合并相同职业
        for (int i = 0; i < nt; i++) {
            int a;
            LL bi;
            cin >> a >> bi;
            professionMap[a] += bi;
        }

        // 提取士兵数量
        for (auto &p : professionMap) {
            b_arr.push_back(p.second);
        }

        // 检查是否可行
        LL total_teams = 0;
        for (LL bi : b_arr) {
            total_teams += bi / 3;
        }
        if (total_teams < k) {
            cout << -1 << '\n';
            continue;
        }

        // 初始选择：每个职业取 min(bi, 2)
        LL ans = 0;
        for (LL &bi : b_arr) {
            LL take = min(bi, 2LL);
            ans += take;
            bi -= take;
        }

        // 分类资源：c3, c2, c1
        LL c3 = 0, c2 = 0, c1 = 0;
        for (LL bi : b_arr) {
            c3 += bi / 3;  // 整除3的商
            LL r = bi % 3;
            if (r == 1) c1++;
            else if (r == 2) c2++;
        }

        // 形成第一个团队
        k--;
        ans++;

        // 使用c3资源（每个团队消耗3士兵）
        if (k > 0) {
            LL v = min(k, c3);
            k -= v;
            ans += v * 3;
        }

        // 使用c2资源（每个团队消耗2士兵）
        if (k > 0) {
            LL v = min(k, c2);
            k -= v;
            ans += v * 2;
        }

        // 使用c1资源（每个团队消耗1士兵）
        if (k > 0) {
            LL v = min(k, c1);
            k -= v;
            ans += v;
        }

        cout << ans << '\n';
    }
    return 0;
}

代码解析

1. ​​输入处理​​：

   • 使用map合并相同职业的士兵数量（职业号可能重复）。
   • 提取士兵数到数组b_arr。

2. ​​可行性检查​​：

   • 计算总团队数total_teams = sum(b_i // 3)，若小于k则输出-1。

3. ​​初始选择​​：

   • 每个职业选择min(b_i, 2)名士兵（避免形成团队）。

4. ​​资源分类​​：

   • c3：剩余士兵数可整除3的职业数。
   • c2：余数为2的职业数。
   • c1：余数为1的职业数。

5. ​​团队形成​​：

   • ​​第一个团队​​：额外选1名士兵（总士兵数+1）。
   • ​​后续团队​​：按优先级使用资源（c3 > c2 > c1），每类资源消耗不同士兵数。

6. ​​输出​​：最终士兵数。

实例验证

1. ​​样例1​​：nt=3, k=2, b_arr=[3,3,3]

   • 总团队数=3 ≥ 2，可行。
   • 初始选择：选2+2+2=6名士兵（剩余：[1,1,1]）。
   • 资源：c1=3，c2=0，c3=0。
   • 团队形成：
     • 第一团队：士兵数=7（选职业1的1名）。
     • 第二团队：使用c1（消耗1名），士兵数=8。
   • 输出：8（正确）。

2. ​​样例2​​：nt=3, k=5, b_arr=[3,3,3]

   • 总团队数=3 < 5，输出-1（正确）。

3. ​​单职业样例​​：nt=1, k=2, b_arr=[6]

   • 总团队数=2 ≥ 2，可行。
   • 初始选择：选2名士兵（剩余4）。
   • 资源：c3=1（4//3=1），c1=1（余1）。
   • 团队形成：
     • 第一团队：士兵数=3。
     • 第二团队：使用c3（消耗3名），士兵数=6。
   • 输出：6（正确）。

注意事项

1. ​​职业合并​​：输入中职业号可能重复，必须用map合并。
2. ​​整数溢出​​：k和士兵数可能很大（k≤1e13），使用long long。
3. ​​资源优先级​​：先使用c3（成本低），再c2和c1。
4. ​​边界情况​​：
   • 小队士兵数不足3时，不提供团队。
   • 当k=0时，直接输出0（代码中由k--和k>0处理）。

测试点设计

1. ​​基本功能​​：

   • 样例1（3小队k=2）：输出8。
   • 样例2（3小队k=5）：输出-1。
   • 单小队（b_i=6, k=2）：输出6。

2. ​​边界测试​​：

   • k=0：输出0。
   • 小队士兵数不足3（b_i=2）：不提供团队。
   • 超大k（k=1e13）和士兵数（b_i=1e15）：验证效率和溢出。

3. ​​特殊场景​​：

   • 所有小队士兵数相同（如b_i=3）。
   • 职业数远小于k（如1个职业，k=100）。
   • 余数分布不均（如c2或c1占主导）。

优化建议

1. ​​效率优化​​：

   • 使用ios::sync_with_stdio(false)加速输入输出。
   • 避免不必要的排序（资源分类无需排序）。
   • 合并相同职业时，map操作O(nt log nt)。

2. ​​代码可读性​​：

   • 用变量名c3、c2、c1代替数组。
   • 注释关键步骤（如资源分类和团队形成）。

3. ​​扩展性​​：

   • 若团队大小变化（如每组4人），调整初始选择（min(b_i, 3)）和资源分类逻辑。