Crying 与选秀 - 题解

标签与难度

标签: 数据结构, 堆, 优先队列, 模拟, Top K 问题, 字符串处理难度: 1400

题目大意喵~

各位观众朋友们晚上好，喵~ 欢迎来到 Crying 主办的选秀大赛！

这次比赛有 $N$ 位选手，他们会按照 $1$ 到 $N$ 的编号顺序依次上场表演，并获得一个在 $[90.0, 100.0]$ 之间的、有7位小数的评分。每个人的分数都是独一无二的哦！

最终只有得分最高的 6 位选手可以晋级。所以，每当一位新选手表演完毕，节目组都想知道TA有没有挤进当前的“前六强”。

我们的任务就是：

统计总共有多少位选手，在他们表演完的那个瞬间，成功进入了当时的前六名。
对于每一位选手，记录下他们是“挤掉”了谁才进入前六的。如果他们没能进入，或者当时前六还没满员，那就算他们没有挤掉任何人（记为0）。

简单来说，就是模拟这个动态更新前六名榜单的过程，并记录下每次变动的情况，喵~

解题思路分析

这道题的核心，就是要高效地维护一个“前六强”的动态排行榜，对吧？每来一位新选手，我们都要拿TA的分数和榜单上的人比较一下。

最朴素的想法可能是，每来一个新选手，就把至今为止所有人的分数放在一起，排个序，然后看看新选手在不在前六。但这样太慢啦！如果有 $N$ 个选手，每次都排序，时间复杂度会飙升到 $O(N^2 \log N)$ ，对于 $N$ 很大的情况，肯定会超时的说。我的猫爪子都要算冒烟了！

我们需要一个更聪明的办法！仔细想想，当一位新选手 i 带着分数 score_i 登场时，我们关心的是什么呢？我们只关心她能不能挤进前六。这取决于她的分数是否比当前前六名中分数最低的那个人要高。

如果 score_i > “前六守门员”的分数，那么恭喜新选手！她成功晋级，而那位可怜的守门员就要被淘汰了。
如果 score_i ≤ “前六守门员”的分数，那她就暂时无缘前六啦。

这个“前六守门员”，就是当前前六名里分数最低的人。所以，我们的问题就转化成了：如何快速找到一个集合中的最小值？

当当当当~ 这时候，就轮到我们的好朋友——优先队列（堆）出场啦！ specifically，我们需要一个小顶堆 (Min-Heap)。

小顶堆是一个神奇的数据结构，它能保证堆顶的元素永远是整个堆里最小的那个。这不就是我们想要的“前六守门员”吗？喵~

所以，我们的策略就是：

维护一个大小最多为 6 的小顶堆，里面存放 (分数, 选手编号) 这样的二元组。小顶堆会根据“分数”来排序。
我们按顺序处理每一位选手 i（从 1 到 $N$ $N$ ）：
- 当堆里的人数还不足 6 个时：说明前六还没满员！新来的选手 i 无条件直接进入前六。我们把她的 (分数, 编号)推进堆里，并且她没有淘汰任何人。
- 当堆里已经有 6 个人时：这时就要进行对决了！我们取出堆顶元素，也就是当前前六名中的最低分 min_score_in_top6。
  - 如果新选手 i 的分数 score_i > min_score_in_top6，那么她更强！我们先弹出堆顶（淘汰守门员），然后把新选手 i 的信息推进堆里。同时，记录下被淘汰的选手的编号。
  - 如果新选手 i 的分数 score_i ≤ min_score_in_top6，那她就暂时无法晋级啦，什么也不用做。

这样一来，对于每个选手，我们只需要进行一次堆操作（插入或替换），效率就非常高啦！

一个小小的提示喵：题目中的分数是7位小数，直接用 double 或 float 类型可能会有讨厌的精度问题。最稳妥的办法是把它们当成字符串读进来，然后去掉小数点，转换成一个大的整数来处理。比如 98.1234567 就变成 981234567，这样比较起来就万无一失了！

代码实现

下面就是我精心为大家准备的C++代码实现啦，注释写得很详细哦，希望能帮到你，喵~

cpp

#include <iostream>
#include <vector>
#include <string>
#include <queue> // 我们的主角：优先队列！
#include <utility> // for std::pair
#include <algorithm> // for std::greater

// 为了方便，我们定义一个类型别名
// first 是分数，second 是选手编号
using Contestant = std::pair<long long, int>;

// 将形如 "98.1234567" 的字符串分数转换为 long long 整数
long long parse_score(const std::string& s) {
    long long integer_part = 0;
    long long decimal_part = 0;
    bool after_dot = false;
    
    for (char c : s) {
        if (c == '.') {
            after_dot = true;
            continue;
        }
        if (!after_dot) {
            integer_part = integer_part * 10 + (c - '0');
        } else {
            decimal_part = decimal_part * 10 + (c - '0');
        }
    }
    
    // 题目保证7位小数，所以直接拼接
    return integer_part * 10000000LL + decimal_part;
}

int main() {
    // 加速输入输出，让程序跑得像小猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    // 创建一个小顶堆。
    // `std::priority_queue` 默认是大顶堆，需要提供比较函数 `std::greater` 使其变为小顶堆。
    std::priority_queue<Contestant, std::vector<Contestant>, std::greater<Contestant>> top_6_heap;

    int entry_count = 0; // 记录进入前六的总人数
    std::vector<int> replaced_by(n + 1, 0); // 记录每位选手淘汰了谁，编号从1到n

    for (int i = 1; i <= n; ++i) {
        std::string score_str;
        std::cin >> score_str;
        long long current_score = parse_score(score_str);

        // Case 1: 前六名还没满员
        if (top_6_heap.size() < 6) {
            top_6_heap.push({current_score, i});
            entry_count++;
            // replaced_by[i] 默认为 0，不用显式设置
        } 
        // Case 2: 前六名已满，需要对决！
        else {
            // 获取当前前六名中的最低分（堆顶）
            Contestant weakest_in_top6 = top_6_heap.top();
            
            if (current_score > weakest_in_top6.first) {
                // 新选手更强！
                entry_count++;
                
                // 记录被淘汰的选手编号
                replaced_by[i] = weakest_in_top6.second;
                
                // 更新堆：淘汰旧人，迎接新人
                top_6_heap.pop();
                top_6_heap.push({current_score, i});
            }
            // else: 新选手分数不够高，无法进入前六，什么也不做
        }
    }

    // 输出结果
    std::cout << entry_count << "\n";
    for (int i = 1; i <= n; ++i) {
        std::cout << replaced_by[i] << (i == n ? "" : " ");
    }
    std::cout << "\n";

    return 0;
}

复杂度分析

时间复杂度: $O(N \log K)$ 对于 $N$ 个选手中的每一个，我们最多执行一次堆的插入 (push) 和一次堆的删除 (pop) 操作。我们维护的堆的大小 $K$ 最大为 6。堆操作的时间复杂度是 $O(\log K)$ 。所以总的时间复杂度是 $O(N \log K)$ 。因为 $K=6$ 是一个很小的常数，所以这个算法的运行时间几乎是线性的，可以认为是 $O(N)$ ，非常高效！
空间复杂度: $O(N)$ 我们主要使用了两个数据结构：
1. 优先队列 top_6_heap，它的大小最多为 $K=6$ ，所以空间是 $O(K)$ 。
2. replaced_by 数组，用来存储 $N$ 个选手的结果，空间是 $O(N)$ 。总的空间复杂度是 $O(N+K)$ ，因为 $N$ 通常远大于 $K$ ，所以我们记为 $O(N)$ 。

知识点总结

优先队列 (堆): 这道题是优先队列的经典应用场景。它能高效地解决动态查找最大/最小元素的问题。要记住，C++ 的 std::priority_queue 默认是大顶堆，要实现小顶堆需要提供 std::greater 作为比较器。
Top K 问题: 这个问题本质上是一个“动态 Top K”问题，即从一个数据流中实时维护前 K 大（或前 K 小）的元素。使用一个大小为 K 的小顶堆来维护前 K 大元素，或者一个大顶堆来维护前 K 小元素，是解决这类问题的标准范式，一定要掌握哦！
数据处理技巧: 在处理带小数的输入时，要警惕浮点数精度问题。将它们转换为整数是一种非常常用且稳健的技巧，可以避免很多不必要的麻烦。
模拟思想: 解题时，首先要准确理解题目的模拟过程。然后，选择合适的数据结构来优化这个过程中的瓶颈操作（比如本题中的“查找最低分”），是算法设计的关键所在。

希望这篇题解能帮助你更好地理解这个问题！继续加油，你一定可以成为算法大师的，喵~

Crying 与选秀 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​