题目描述

我们需要为一家企业整理一份优秀学生推荐名单。学生从参加天梯赛的人中选出。推荐过程遵循以下规则：

1. 资格: 只有天梯赛得分不低于 175 分的学生才会被考虑。
2. 批次: 最多接受 $K$ 批推荐名单。
3. 批内规则 (主要): 同一批名单上的学生，其天梯赛成绩原则上应 严格递增。
4. 批内规则 (例外): 如果一个学生的成绩与名单上前一个被推荐的学生成绩相同，但该学生的 PAT 考试成绩达到了企业的面试分数线 $S$，那么这个学生也可以被推荐（作为额外名额）。
5. 目标: 找出通过这 $K$ 批推荐，最多能推荐多少学生。

样例

输入:
10 2 90
203 0
169 91
175 88
175 0
175 90
189 0
189 0
189 95
189 89
256 100

输出:
8

样例解释

• 第一批:

  • 可选基础学生 (严格递增):
    • 175 分 (选 1 人)
    • 189 分 (选 1 人)
    • 203 分 (选 1 人)
    • 256 分 (选 1 人)
  • 应用例外规则:
    • 对于 175 分，之前没有学生，不能用例外。但可以检查 PAT >= 90 的。有一个 175 分 PAT=90 的学生，可以额外加入。
    • 对于 189 分，前一个选的是 175 分，分数不同，不能用例外。但是，有一个 189 分 PAT=95 的学生，可以在 189 分被选中之后，作为额外名额加入。
    • 对于 203 分，前一个是 189，分数不同。
    • 对于 256 分，前一个是 203，分数不同。
  • 第一批实际可选：
    • 175 分基础 1 人 + 175 分 PAT 例外 1 人 = 2 人
    • 189 分基础 1 人 + 189 分 PAT 例外 1 人 = 2 人
    • 203 分基础 1 人 = 1 人
    • 256 分基础 1 人 = 1 人
  • 第一批共 2 + 2 + 1 + 1 = 6 人。
  • 剩余学生情况：169(不合格), 175(剩1人, PAT=0/88), 189(剩1人, PAT=0/89)

• 第二批:

  • 可选基础学生 (严格递增):
    • 175 分 (选 1 人)
    • 189 分 (选 1 人)
  • 应用例外规则:
    • 对于 175 分，没有 PAT>=90 的了。
    • 对于 189 分，没有 PAT>=90 的了。
  • 第二批共 1 + 1 = 2 人。

• 总人数: 6 + 2 = 8 人。

(注：样例解释的理解可能与代码逻辑略有出入，以代码逻辑为准进行分析)

算法 (贪心 + 模拟)

时间复杂度 $O(N \log N + K \cdot M)$，其中 M 为不同分数档的数量

思路分析

这是一个最大化推荐人数的问题，涉及到多批次选择和带有例外的递增规则。由于我们希望总人数最多，并且有 K 次机会（批次），这通常暗示着可以使用贪心策略。

1. 预处理:

   • 首先，筛选出所有天梯赛分数不低于 175 的学生。
   • 对于这些符合资格的学生，我们需要按天梯赛分数进行分组。
   • 对于每个分数档次 score，我们需要统计两个信息：
     • total_count: 该分数档次的总人数。
     • pat_qualified_count: 该分数档次中，PAT 成绩 $\ge S$ 的人数。
   • 使用 std::map<int, pair<int, int>> score_count 是一个很好的选择。键 (key) 是天梯赛分数，值 (value) 是一个 pair {total_count, pat_qualified_count}。map 会自动按分数排序，方便后续处理。

2. 模拟 K 个批次:

   • 我们需要模拟 $K$ 轮推荐过程。每一轮（批次）都应该尽可能多地推荐学生。
   • 使用一个循环 for (int batch = 0; batch < k; batch++) 来模拟批次。

3. 单批次内的贪心选择:

   • 在一批推荐中，核心规则是分数严格递增。例外规则允许在分数相同时加入 PAT 合格者。
   • 为了最大化人数，我们应该在满足规则的前提下，从低分到高分贪心地选择学生。
   • 迭代: 遍历 score_count 中的所有分数档次（map 保证了按分数升序）。
   • 状态: 在处理当前批次时，需要维护一个变量 prev_score，记录上一个通过主要规则（严格递增）选入该批次的学生的分数。初始化 prev_score = -1。
   • 选择逻辑:
     a. 对于当前分数档次 current_score：
     b. 主要规则检查: 如果 current_score > prev_score：
     i. 检查该分数档次是否还有剩余学生 (score_count[current_score].first > 0)。
     ii. 如果有，则选择 1 名学生。将总推荐人数 total 加 1，并将 score_count[current_score].first 减 1。更新 prev_score = current_score。
     iii. 立即应用例外规则: 在选了这名基础学生后，检查同一分数档次 current_score 是否还有 PAT 合格的剩余学生可以额外加入。可以额外加入的人数 extra 等于当前分数档次中 剩余的 PAT 合格人数 (score_count[current_score].second) 和 剩余的总人数 (score_count[current_score].first) 中的较小值 (extra = min(pat_qualified_count, total_count_remaining)）。
     iv. 将 total 增加 extra。
     v. 将 score_count[current_score].first 减少 extra。
     vi. 将 score_count[current_score].second 减少 extra (因为这些 PAT 合格的学生也被用掉了)。
     c. 如果 current_score <= prev_score，则根据主要规则不能选择该分数的学生作为新的基础学生，跳过主要规则选择。例外规则仅在选定一个基础学生后，针对该基础学生的分数生效，而不是独立生效。

4. 数据结构优化:

   • 直接在 map 上修改计数值可能效率略低，且迭代器可能失效。更好的方法是在开始模拟前，将 map 的内容复制到一个 std::vector<pair<int, pair<int, int>>> scores 中。这样可以方便地通过索引访问和修改计数值。vector 保持了从 map 复制过来的有序性。

5. 终止条件:

   • 模拟 $K$ 个批次后结束。
   • 如果在某一批次中没有推荐任何学生，说明所有符合条件的学生都已被推荐，可以提前结束循环。

6. 代码逻辑解读:

   • map<int, pair<int, int>> score_count: 用于初始统计。
   • vector<pair<int, pair<int, int>>> scores: 将 map 数据转存到 vector，m 是不同分数档的数量。
   • total = 0: 记录总推荐人数。
   • 外层循环 for (int batch = 0; batch < k && m > 0; batch++): 模拟 K 个批次，m > 0 是个小优化（如果没分数档了就停止）。
   • prev = -1: 记录本批次上一个被选中的分数。
   • 内层循环 for (int i = 0; i < m; i++): 遍历 vector 中的分数档次。
   • if (curr <= prev) continue;: 执行主要规则检查。
   • if (!used[i] && scores[i].second.first > 0): 这里的 used 数组在代码中似乎有些多余和令人困惑。 正确的逻辑应该是只检查 scores[i].second.first > 0。如果大于 0，就执行选择。我们假设忽略 used[i] 的判断，因为它不符合贪心逻辑。
   • total++; scores[i].second.first--; prev = curr;: 选择 1 名基础学生，更新计数和 prev。
   • int extra = min(scores[i].second.second, scores[i].second.first);: 计算可额外添加的 PAT 合格人数。
   • if (extra > 0 && scores[i].first == prev): 这里的 scores[i].first == prev 条件也是冗余的，因为我们刚把 prev 更新为 scores[i].first。只需要 if (extra > 0)。
   • total += extra; scores[i].second.first -= extra; scores[i].second.second -= extra;: 添加额外学生，更新两个计数。
   • 最终输出 total。

时间复杂度

• 读取输入并填充 map：$O(N \log N)$ （如果用 unordered_map 再排序是 $O(N)$ 平均）。
• 将 map 转换为 vector：$O(M)$，其中 $M$ 是不同分数档的数量 ($M \le N$，且 $M$ 最多约 290）。
• 模拟 K 个批次：外层循环 K 次。
• 每个批次内遍历 M 个分数档：内层循环 M 次。
• 总复杂度：$O(N \log N + K \cdot M)$。考虑到 $N \le 10^5, K \le 5000, M \approx 290$，这个复杂度是可以通过的。

空间复杂度

• score_count (map): $O(M)$。
• scores (vector): $O(M)$。
• 总空间复杂度：$O(M)$。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

using namespace std;
using i64 = long long; // 定义 i64 为 long long 的别名 (本题未使用)

int main() {
    // 加速 IO
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k, s; // n: 学生数, k: 批次数, s: PAT 分数线
    cin >> n >> k >> s;

    // 使用 map 统计每个有效分数 (>=175) 的信息
    // map[ladder_score] = {total_count, pat_qualified_count}
    map<int, pair<int, int>> score_count; 
    for (int i = 0; i < n; i++) {
        int ladder, pat;
        cin >> ladder >> pat;
        // 只考虑天梯赛分数 >= 175 的学生
        if (ladder >= 175) {
            score_count[ladder].first++; // 该分数总人数 +1
            // 如果 PAT 分数达标，PAT 合格人数 +1
            if (pat >= s) score_count[ladder].second++; 
        }
    }

    // 将 map 数据转存到 vector 中，方便迭代和修改
    // vector<pair<分数, pair<总人数, PAT合格人数>>>
    vector<pair<int, pair<int, int>>> scores(score_count.begin(), score_count.end());
    int m = scores.size(); // 不同分数档的数量

    int total = 0; // 记录总推荐人数
    // 模拟 k 个批次的推荐
    for (int batch = 0; batch < k && m > 0; batch++) { 
        // vector<bool> used(m, false); // 这个 used 数组在代码中逻辑似乎不必要，忽略它
        int prev = -1; // 记录本批次上一个按主要规则选中的学生分数，初始化为 -1

        // 遍历所有分数档次 (vector 保持了 map 的有序性)
        for (int i = 0; i < m; i++) {
            int curr = scores[i].first; // 当前分数
            // 检查主要规则：当前分数必须严格大于上一个选中的分数
            if (curr <= prev) continue; // 不满足严格递增，跳过

            // 尝试按主要规则选择一个学生
            // 检查当前分数档次是否还有学生
            // if (!used[i] && scores[i].second.first > 0) { // 忽略 !used[i]
            if (scores[i].second.first > 0) { 
                // used[i] = true; // 标记这个分数档在本批次被用作基础选择点（但这个标记似乎没用）
                total++; // 总推荐人数 +1
                scores[i].second.first--; // 该分数档总人数 -1
                prev = curr; // 更新本批次上一个选中的分数

                // 立即应用例外规则：为当前分数档添加 PAT 合格的额外学生
                // 计算可以额外添加的人数 = min(剩余 PAT 合格人数, 剩余总人数)
                int extra = min(scores[i].second.second, scores[i].second.first);
                // if (extra > 0 && scores[i].first == prev) { // scores[i].first == prev 是冗余的
                if (extra > 0) {
                    total += extra; // 增加总推荐人数
                    scores[i].second.first -= extra; // 减少总人数
                    scores[i].second.second -= extra; // 减少 PAT 合格人数
                }
            }
        }
        // // 可选优化：如果这一批一个学生都没选上，后续批次也选不上了
        // if (prev == -1) { // 检查是否该批次有选择
        //     break; 
        // }
    }

    // 输出最终的总推荐人数
    cout << total << "\n";
    return 0; // 程序正常结束
}